package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 779. K-th Symbol in Grammar
 *
 * 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)].
 */

public class _779 {
  public static class Solution1 {
    /**Time: O(2^n)
     * Space: O(2^n)
     * This will result int TLE.*/
    public int kthGrammar(int N, int K) {
      List<List<Integer>> lists = new ArrayList<>();
      lists.add(Arrays.asList(0));
      for (int i = 1; i <= N; i++) {
        List<Integer> curr = new ArrayList<>();
        List<Integer> prev = lists.get(i - 1);
        for (int j = 0; j < prev.size(); j++) {
          if (prev.get(j) == 0) {
            curr.add(0);
            curr.add(1);
          } else {
            curr.add(1);
            curr.add(0);
          }
        }
        lists.add(curr);
      }
      return lists.get(N).get(K - 1);
    }
  }

  public static class Solution2 {
    /**Time: O(logn)
     * Space: O(1)*/
    public int kthGrammar(int N, int K) {
      return Integer.bitCount(K - 1) % 2;
    }

  }

}

@@ -110,648 +110,8 @@
 t;%0A%0A
-/**%0A * 779. K-th Symbol in Grammar%0A *%0A * On the first row, we write a 0. Now in every subsequent row,%0A * we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.%0A * Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).%0A%0A Examples:%0A Input: N = 1, K = 1%0A Output: 0%0A%0A Input: N = 2, K = 1%0A Output: 0%0A%0A Input: N = 2, K = 2%0A Output: 1%0A%0A Input: N = 4, K = 5%0A Output: 1%0A%0A Explanation:%0A row 1: 0%0A row 2: 01%0A row 3: 0110%0A row 4: 01101001%0A%0A Note:%0A%0A N will be an integer in the range %5B1, 30%5D.%0A K will be an integer in the range %5B1, 2%5E(N-1)%5D.%0A */%0A%0A
 publ
@@ -126,16 +126,18 @@
  _779 %7B%0A
+  
   public
@@ -162,27 +162,43 @@
 tion1 %7B%0A    
-/**
+    /**%0A         * 
 Time: O(2%5En)
@@ -194,24 +194,28 @@
 ime: O(2%5En)%0A
+    
      * Space
@@ -228,16 +228,20 @@
 n)%0A     
+    
 * This w
@@ -259,19 +259,33 @@
 int TLE.
+%0A         
 */%0A
+    
     publ
@@ -314,24 +314,30 @@
 N, int K) %7B%0A
+      
       List%3CL
@@ -379,24 +379,30 @@
 %3C%3E();%0A      
+    
+  
 lists.add(Ar
@@ -420,24 +420,30 @@
 (0));%0A      
+     
+ 
 for (int i =
@@ -461,32 +461,40 @@
  i++) %7B%0A        
+      
+  
 List%3CInteger%3E cu
@@ -517,32 +517,40 @@
 st%3C%3E();%0A        
+     
+   
 List%3CInteger%3E pr
@@ -572,32 +572,40 @@
 i - 1);%0A        
+   
+     
 for (int j = 0; 
@@ -638,16 +638,26 @@
         
+         
+ 
 if (prev
@@ -668,24 +668,36 @@
 (j) == 0) %7B%0A
+            
             
@@ -713,32 +713,44 @@
 0);%0A            
+ 
+           
 curr.add(1);%0A   
@@ -756,16 +756,26 @@
         
+   
+       
 %7D else %7B
@@ -779,32 +779,44 @@
 e %7B%0A            
+      
+      
 curr.add(1);%0A   
@@ -816,32 +816,44 @@
 1);%0A            
+        
+    
 curr.add(0);%0A   
@@ -841,32 +841,42 @@
    curr.add(0);%0A
+          
           %7D%0A    
@@ -871,34 +871,50 @@
       %7D%0A        
-%7D%0A
+        %7D%0A        
         lists.ad
@@ -928,24 +928,36 @@
 ;%0A      
-%7D%0A
+      %7D%0A     
       
+ 
 return l
@@ -988,15 +988,23 @@
     
-%7D%0A
+    %7D%0A  
   %7D%0A%0A
+  
   pu
@@ -1037,19 +1037,35 @@
 2 %7B%0A    
-/**
+    /**%0A         * 
 Time: O(
@@ -1071,24 +1071,28 @@
 (logn)%0A     
+   
+ 
 * Space: O(1
@@ -1092,23 +1092,37 @@
 ce: O(1)
-*/%0A
+%0A         */%0A   
     
+ 
 public i
@@ -1147,24 +1147,30 @@
 N, int K) %7B%0A
+      
       return
@@ -1199,22 +1199,28 @@
 1) %25 2;%0A
+    
     %7D%0A%0A
+  
   %7D%0A%0A%7D%0A

refactor 779