KthSymbolInGrammar [source code]

public class KthSymbolInGrammar {
static
/******************************************************************************/
class Solution {
    public int kthGrammar(int N, int K) {
        if (N == 1)
            return 0;
        int len = 1 << (N - 1);
        int prev = kthGrammar (N - 1, (K - 1) % (len / 2) + 1);
        return (K - 1) < len / 2 ? prev : 1 - prev;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        KthSymbolInGrammar.Solution tester = new KthSymbolInGrammar.Solution();
        int[] inputs = {
            1,1,0,
            2,1,0,
            2,2,1,
            4,5,1,
            3,2,1,
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int N = inputs[3 * i], K = inputs[3 * i + 1], ans = inputs[3 * i + 2];
            System.out.println (Printer.separator ());
            int output = tester.kthGrammar (N, K);
            System.out.printf ("%d and %d -> %s, expected: %d\n", 
                N, K, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

contest的时候大概观察了规律之后写的算法; 注意, power of 2用shift来计算这个应该是常规操作了, 最后速度是5ms (NA).

题目本身的思路不是特别难; 简单的就是直接笔算, 总结规律, 然后大概就能看到一个递归的思路; 注意这里的1based和0based的转换, 注意我recursion往下传的时候, 是先转化成为1based的, 然后函数本身内部的逻辑处理的时候都是0based的;

editorial

Approach #1: Brute Force [Time Limit Exceeded]

Intuition and Algorithm

We'll make each row exactly as directed in the problem statement. We only need to remember the last row.

Unfortunately, the strings could have length around 1 billion, as they double on each row, so this approach is not efficient enough.

class Solution {  
    public int kthGrammar(int N, int K) {  
        int[] lastrow = new int[1 << N];  
        for (int i = 1; i < N; ++i) {  
            for (int j = (1 << (i-1)) - 1; j >= 0; --j) {  
                lastrow[2*j] = lastrow[j];  
                lastrow[2*j+1] = 1 - lastrow[j];  
            }  
        }  
        return lastrow[K-1];  
    }  
}

Approach #2: Recursion (Parent Variant) [Accepted]

Intuition and Algorithm

Since each row is made only using information from the previous row, let's try to write the answer in terms of bits from the previous row.

Diagram of digits with relationship to their parent
In particular, if we write say "0110" which generates "01101001", then the first "0" generates the first "01" in the next row; the next digit "1" generates the next "10", the next "1" generates the next "10", and the last "0" generates the last "01".

Diagram of digits through repeated function calls
In general, the Kth digit's parent is going to be (K+1) / 2. If the parent is 0, then the digit will be the same as 1 - (K%2). If the parent is 1, the digit will be the opposite, ie. K%2.

class Solution {  
    public int kthGrammar(int N, int K) {  
        if (N == 1) return 0;  
        return (~K & 1) ^ kthGrammar(N-1, (K+1)/2);  
    }  
}

写的很简洁的一个写法, 思路也和清晰; 这里的这个 (k+1)/2应该是不难理解的, 如果K是7, 那么我们就要算出来8, 然后/2, 如果K是8, 那么+的1在/2的时候直接也被无视了; 当然, 你也可以跟他一样直接画图找规律: 很多时候就是先有一个大概的intuition(比如这里的divide找parent), 然后实际的算式最方便的做法就是直接观察找规律, 而不是完全从理论上面去推导;

xor完成的是一个奇偶性判断的对应操作;

注意这个方法跟我自己的方法一样, 复杂度其实是O(N), 而不是O(lgN), 因为虽然arg2一直在/2, arg1是一直-1的;

Approach #3: Recursion (Flip Variant) [Accepted]

Intuition and Algorithm

As in Approach #2, we could try to write the bit in terms of it's previous bit.

When writing a few rows of the sequence, we notice a pattern: the second half is always the first half "flipped": namely, that '0' becomes '1' and '1' becomes '0'.

这也是我找到这个规律的思路;

We can prove this assertion by induction. The key idea is if a string X generates Y, then a flipped string X′ generates Y′.

This leads to the following algorithm idea: if K is in the second half, then we could put K -= (1 << N-2) so that it is in the first half, and flip the final answer.

class Solution {  
    public int kthGrammar(int N, int K) {  
        if (N == 1) return 0;  
        if (K <= 1 << N-2)  
            return kthGrammar(N-1, K);  
        return kthGrammar(N-1, K - (1 << N-2)) ^ 1;  
    }  
}

他的逻辑则是全部用1based的来处理, 实际上也没有问题; 注意他用xor来完成flip;

Approach #4: Binary Count [Accepted]

Intuition and Algorithm

As in Approach #3, the second half of every row is the first half flipped.

When the indexes K are written in binary (now indexing from zero), indexes of the second half of a row are ones with the first bit set to 1.

This means when applying the algorithm in Approach #3 virtually, the number of times we will flip the final answer is just the number of 1s in the binary representation of K-1.

class Solution {  
    public int kthGrammar(int N, int K) {  
        return Integer.bitCount(K - 1) % 2;  
    }  
}

这个解法在contest里面看到不少人就是用的这个, 当时没有看懂; awice这里给的解释其实也比较的imperative: 是在#3的基础上分析出来的, #3实际上就是不停的/2, 然后如果得到的当前bit是1, 那么就flip结果, 所以最后其实跟bit count是一个效果;

这里的复杂度认为是lgN, 也就是说bitCount认为是一个比较直接的实现方式; 如果考虑int, 那么可以认为这里是O(1)的复杂度;

@zestypanda said in C++ with explanation, three solutions O(n), O(logn), and O(loglogn):

Brute force O(n) TLE

class Solution {  
public:  
    int kthGrammar(int N, int K) {  
        string s = "0";  
        for (int i = 1; i < N; ++i) {  
            string t;  
            for (char c : s) {  
                if (c == '0')  
                   t += "01";  
                else  
                   t += "10";  
            }  
            swap(s, t);  
        }  
        return s[K-1]-'0';  
    }  
};

The structure is like a full tree.
0 ==> 01; 1 ==> 10; so if only if K%2 == 0, result(K) == result(K/2);
The key is whether the set bits of (K-1) is odd or even
O(logn) 3ms

class Solution {  
public:  
    int kthGrammar(int N, int K) {  
        K--;  
        int cnt = 0;  
        while (K) {  
            cnt += K&1;  
            K >>= 1;  
        }  
        return cnt%2;  
    }  
};

If we only care about the set bits are odd or even, there is an O(loglogn) solution.
Although O(loglogn) may be meaningless here, because logn is at most 32. Let's assume K is m bits long.

class Solution {  
public:  
    int kthGrammar(int N, int K) {  
       K--;  
       int m = 32;  
       while (m > 1) {  
          m = (m + 1) >> 1;  
          K = K ^ (K >> m);  
          K &= (1 << m) - 1;  
       }  
       return K & 1;  
    }  
};

最后这个算法之所以是loglogn是因为这里的这个算法其实是logm, 然后m是logn;

至于这个算法的原理, 一开始也是没看懂, 但是后面大概看懂了, 实际上就是不停的把K进行对折, 然后对折的两半进行xor; 然后只保留对折后的长度的结果; 这个操作的作用就是比如你对比1000_1011和0000_1011, 你就可以看到, 第一个数字在[3]和[7]的位置的两个1就进行了对位消除, 而其他没有对位的1, 全部都被自动保留; 在不停的对折的过程当中, 所有的1几乎都被不停的对位消除, 最后要么只剩下一个1, 要么只剩下一个0;

@grandyang said in My 3 lines C++ recursive solution:

The whole structure can be viewed a binary tree, when a node is 0, their two children nodes are 0 and 1, similarly, when a node is 1, two children nodes are 1 and 0. We can know whether the position of K is a left node or a right node by dividing 2. If K is even, current node is right child, and its parent is the (K/2)th node in previous row; else if K is odd, current node is left child and its parent is the ((K+1)/2)th node in previous row.
The value of current node depends on its parent node, without knowing its parent node value, we still cannot determine current node value. That's why we need recursion, we keep going previous row to find the parent node until reach the first row. Then all the parent node value will be determined after the recursion function returns.

class Solution {  
public:  
    int kthGrammar(int N, int K) {  
  if (N == 1) return 0;  
  if (K % 2 == 0) return (kthGrammar(N - 1, K / 2) == 0) ? 1 : 0;  
  else return (kthGrammar(N - 1, (K + 1) / 2) == 0) ? 0 : 1;  
    }  
};

@lkjhgfdsa said in My 3 lines C++ recursive solution:

@grandyang Could you please tell the intuition behind working with the even and odd values of k? When I was solving it during the contest, I never thought that this would be somehow related to the parity of k! I coded up a solution like a level-order traversal of a tree and then tried to optimize it by caching (of course, I couldn't succeed!)

Appreciate your help!

讲白了, 这个题目多少巧妙的方法, 都得首先建立在你肯观察规律的前提上;

一个对bit count做法的解释:

@cks said in Python 1-line:

Note that when N is increased by 1, the sequence extends by flipping itself, e.g. 0110 -> 0110 1001. Those extended Ks are exactly the originals with a prefixing 1 in their binary representations, which exactly changes the parity of the number of 1s. By writing down a few examples you can get my conclusion yourself.

好像有点道理; 至少给了一个稍微declarative一点的方向;

另一个:

@vinceX said in [JAVA] one line:

That's the explanation;

没有submission;

contest也没有看到特别神奇的解法;

Problem Description

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:

Input: N = 1, K = 1  
Output: 0  

Input: N = 2, K = 1  
Output: 0  

Input: N = 2, K = 2  
Output: 1  

Input: N = 4, K = 5  
Output: 1  

Explanation:  
row 1: 0  
row 2: 01  
row 3: 0110  
row 4: 01101001

Note:

N will be an integer in the range [1, 30].
K will be an integer in the range [1, 2^(N-1)].

Difficulty:Medium
Total Accepted:1.8K
Total Submissions:5.9K
Contributor:awice
Companies
google
Related Topics
recursion

LC795 KthSymbolInGrammar

KthSymbolInGrammar [source code]

editorial

Approach #1: Brute Force [Time Limit Exceeded]

Approach #3: Recursion (Flip Variant) [Accepted]

Approach #4: Binary Count [Accepted]

Problem Description

results matching ""

No results matching ""