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)].
class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         stack = []
         for num in arr:
             if len(stack)==0 or stack[-1] <= num:
                 stack.append(num)
             else:
                 maxnum = stack.pop()
                 while len(stack)>0 and stack[-1]>num:
                     stack.pop()
                 stack.append(maxnum)
         return len(stack)
class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         stack = []
         for num in arr:
             if len(stack)==0 or stack[-1] <= num:
                 stack.append(num)
             else:
                 maxnum = stack.pop()
                 while len(stack)>0 and stack[-1]>num:
                     stack.pop()
                 stack.append(maxnum)
         return len(stack)