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)].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Complete search

Starter code: class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        

Solutions:
class Solution:

	def maxChunksToSorted(self, arr):
		res = 0
		temp = sorted(arr)
		(sum1, sum2) = (0, 0)
		for i in range(0, len(arr)):
			sum1 += arr[i]
			sum2 += temp[i]
			if sum1 == sum2:
				res += 1
		return res


class Solution:

	def maxChunksToSorted(self, arr):
		(mxvs, mnvs) = ([-1] * len(arr), [10 ** 8 + 1] * len(arr))
		for (i, v) in enumerate(arr):
			if i == 0:
				mxvs[i] = arr[i]
			else:
				mxvs[i] = max(mxvs[i - 1], v)
		for i in range(len(arr))[::-1]:
			if i == len(arr) - 1:
				mnvs[i] = arr[i]
			else:
				mnvs[i] = min(mnvs[i + 1], arr[i])
		cnt = 0
		for i in range(len(arr)):
			if mxvs[i] <= (mnvs[i + 1] if i < len(arr) - 1 else 10 ** 8 + 1):
				cnt += 1
		return cnt


class Solution:

	def maxChunksToSorted(self, arr):
		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):
		arr_index = sorted(list(range(len(arr))), key=arr.__getitem__)
		ans = ma = 0
		for (i, x) in enumerate(arr_index):
			ma = max(ma, x)
			if ma == i:
				ans += 1
		return ans


class Solution:

	def maxChunksToSorted(self, arr):
		stack = []
		for e in reversed(arr):
			min_so_far = e
			while True:
				if len(stack) == 0 or e <= stack[-1][0]:
					stack.append([min_so_far, e])
					break
				if e > stack[-1][1]:
					min_so_far = min(min_so_far, stack.pop()[0])
				else:
					stack[-1][0] = min(min_so_far, stack[-1][0])
					break
		return len(stack)


class Solution:

	def maxChunksToSorted(self, arr):
		sarr = sorted(arr)
		table = {}
		for (i, n) in enumerate(sarr):
			if n not in table:
				table[n] = [i, i]
			else:
				table[n][1] += 1
		c = -1
		chunks = 0
		for (i, n) in enumerate(arr):
			c = max(c, table[n][0])
			if table[n][0] < table[n][1]:
				table[n][0] += 1
			if c == i:
				chunks += 1
		return chunks


class Solution:

	def maxChunksToSorted(self, arr):
		if arr is None:
			return 0
		if len(arr) < 2:
			return len(arr)
		suffix_min = [float('inf')] * len(arr)
		suffix_min[-1] = arr[-1]
		suffix_max = [float('-inf')] * len(arr)
		suffix_max[-1] = arr[-1]
		for index in range(len(arr) - 2, -1, -1):
			suffix_min[index] = min(arr[index + 1], suffix_min[index + 1])
			suffix_max[index] = max(arr[index + 1], suffix_max[index + 1])
		index = 0
		chunk_count = 0
		print(suffix_min)
		while index < len(arr):
			chunk_count += 1
			if arr[index] > suffix_min[index]:
				j = index
				running_max = arr[j]
				while j < len(arr) and running_max > suffix_min[j]:
					running_max = max(running_max, arr[j])
					j += 1
				index = j + 1
			else:
				index += 1
		return chunk_count


class Solution:

	def maxChunksToSorted(self, arr):
		t = arr[0]
		left_max = []
		for x in arr:
			t = max(t, x)
			left_max.append(t)
		t = arr[-1]
		right_min = []
		for i in range(len(arr) - 1, -1, -1):
			t = min(arr[i], t)
			right_min.append(t)
		count = 1
		for i in range(0, len(arr) - 1):
			if left_max[i] <= right_min[len(arr) - i - 2]:
				count += 1
		return count


class Solution:

	def maxChunksToSorted(self, arr):
		dict = {}
		sortedArr = sorted(arr)
		for i in range(len(sortedArr)):
			if sortedArr[i] not in dict:
				dict[sortedArr[i]] = [i]
			else:
				dict[sortedArr[i]].append(i)
		position = []
		for (i, val) in enumerate(arr):
			position.append(dict[val][0] - i)
			dict[val].pop(0)
		maxNum = 0
		i = 0
		ifPlusMinus = 0
		maxIdealPosition = 0
		while i < len(position):
			if position[i] == 0 and ifPlusMinus == 0:
				maxNum += 1
				i += 1
			elif position[i] > 0 and ifPlusMinus == 0:
				ifPlusMinus = 1
				maxIdealPosition = i + position[i]
				i += 1
			elif position[i] >= 0 and ifPlusMinus == 1:
				if i + position[i] > maxIdealPosition:
					maxIdealPosition = i + position[i]
				i += 1
			elif position[i] < 0 and ifPlusMinus == 1:
				if i < len(position) - 1:
					if position[i + 1] < 0:
						i += 1
					elif position[i + 1] >= 0:
						if i == maxIdealPosition:
							maxNum += 1
							ifPlusMinus = 0
							maxIdealPosition = 0
						i += 1
				else:
					maxNum += 1
					ifPlusMinus = 0
					i += 1
		return maxNum


class Solution:

	def maxChunksToSorted(self, arr):
		from collections import Counter
		s = sorted(arr)
		i = 0
		a_nums = Counter()
		b_nums = Counter()
		total = 0
		while i < len(arr):
			a_nums[arr[i]] += 1
			b_nums[s[i]] += 1
			if a_nums == b_nums:
				a_nums.clear()
				b_nums.clear()
				total += 1
			i += 1
		return total