0

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

Link to the Problem: https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/1675/

Solution:

class Solution {
public:
    int kthGrammar(int N, int K) {
        if(N==0||K==0)
            return 0;
        
        string result="0";
        string finals;
        int i,j;
        for(j=0;j<N-1;j++)
        {
            
            for(i=0;i<result.length();i++)
            {
                if(result[i]=='0')
                    finals.append("01");
                else
                    finals.append("10");
            }
            result=finals;
            
        }
        return result[K-1]-'0';
    }
};
kaylum
  • 13,833
  • 2
  • 22
  • 31
Himanshu Ranjan
  • 282
  • 1
  • 7
  • 22
  • C tag removed. Please note that C and C++ are different languages. – kaylum Sep 08 '20 at 07:02
  • 2
    For your code I would expect TLE instead of failed test cases. Please double check. – Yunnosch Sep 08 '20 at 07:07
  • Print `result` on every iteration through the loop. Compare your N=4, K=5 with the example. – molbdnilo Sep 08 '20 at 07:13
  • 2
    Now that OP has accepted an answer, let me mention https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer I think it is the fastest way, in case that TLE turns out to be the next problem. – Yunnosch Sep 08 '20 at 07:23
  • 1
    Concerning efficiency: look at the first rows, and try to rely the results to the binary representation of K, assuming zero indexing for K. – Damien Sep 08 '20 at 07:23
  • Yes,TLE is a problem here. I solved it using recursion now.Its just that I try to implement a basic approach first.Thanks! – Himanshu Ranjan Sep 08 '20 at 07:24

2 Answers2

1

Your finals string remains with old contents. Seems you need to clear it at every loop turn.

Anyway, your approach is not suitable for large inputs - so instead of (huge) string generation consider calculation of needed symbol with some math.

MBo
  • 77,366
  • 5
  • 53
  • 86
  • but I am appending on every loop,why do i need to clear it? – Himanshu Ranjan Sep 08 '20 at 07:14
  • This task assumes length doubling at every outer loop. But you make triple length ("01"=>current "01" + new "01" + new"10" = "010110") – MBo Sep 08 '20 at 07:17
  • Note that current string will be start of new string, so you can keep current `finals` and append only treatment for the second half of string. – MBo Sep 08 '20 at 07:20
0
def f(n,k):
   if n == 1:
     return 0
   if k<=pow(2,n-2):
     return f(n-1,k)
   else:
     return 1-f(n-1,k-(pow(2,n-2)))

the above is a better soln. written in python but same logic can be used

ashik alias
  • 9
  • 4
  • You offer a working solution to the actual problem instead of answering the question. This is ok, but the answer would be better if you explain, how your solution works and why it is preferable. – grek40 Sep 08 '20 at 12:59