779. K-th Symbol in Grammar

779. K-th Symbol in Grammar

Nth row  = (N-1)th row + (n-1)th Inverse.

Example;
1st row = 0
2nd row = 1st row + 1st row Inverse (01)

Every row will power of two.

Solution:

class Solution {
public:
    int kthGrammar (int N, int k)
{
  long s = 1 << (N - 1), flips = 0;

  while(s > 2){
    if(k > s/2){
      k -= s/2;
      flips++;
    }
    s /= 2;
  }
  k--;
  //cout << "---------"<<k<<endl;
  if(flips&1)k = 1 - k;
  return k;
}
};

Share: