Given two integers m & n, find the number of possible sequences of length n such that each of the next element is greater than or equal to twice of the previous element but less than or equal to m.
Example 1:
Input: m = 10, n = 4
Output: 4
Explaination: There should be n elements and 
value of last element should be at-most m. 
The sequences are {1, 2, 4, 8}, {1, 2, 4, 9}, 
{1, 2, 4, 10}, {1, 2, 5, 10}.
Example 2:
Input: m = 5, n = 2
Output: 6
Explaination: The sequences are {1, 2}, 
{1, 3}, {1, 4}, {1, 5}, {2, 4}, {2, 5}.
Your Task:
You do not need to read input or print anything. Your task is to complete the function numberSequence() which takes the number m and n as input parameters and returns the number of sequences.
Expected Time Complexity: O(m*n)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ m, n ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Divide and conquer

Starter code: #User function Template for python3

class Solution:
    def numberSequence(self, m, n):
        # code here

Solutions:
class Solution:

	def numberSequence(self, m, n):
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		dp[1] = [1] * m
		for seq in range(2, n + 1):
			for num in range(1, m + 1):
				if num < seq:
					dp[seq][num] = 0
				else:
					dp[seq][num] = sum(dp[seq - 1][1:num // 2 + 1])
		return sum(dp[-1])


class Solution:

	def numberSequence(self, m, n):
		if m < n:
			return 0
		if n == 0:
			return 1
		return self.numberSequence(m - 1, n) + self.numberSequence(m >> 1, n - 1)


class Solution:

	def numberSequence(self, m, n):
		if m < n:
			return 0
		if n == 0:
			return 1
		ans = self.numberSequence(m - 1, n) + self.numberSequence(m // 2, n - 1)
		return ans


class Solution:

	def numberSequence(self, m, n, curr=1, idx=1):
		count = 0
		if idx == n:
			while curr <= m:
				curr += 1
				count += 1
			return count
		while curr * 2 ** (n - idx) <= m:
			count += self.numberSequence(m, n, curr * 2, idx + 1)
			curr += 1
		return count


class Solution:

	def numberSequence(self, m, n):
		T = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					T[i][j] = 0
				elif j == 1:
					T[i][j] = i
				else:
					T[i][j] = T[i - 1][j] + T[i // 2][j - 1]
		return T[m][n]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def f(self, num, k):
		if num < k:
			return 0
		if k == 0:
			return 1
		if (num, k) in self.tb:
			return self.tb[num, k]
		ways = self.f(num // 2, k - 1) + self.f(num - 1, k)
		self.tb[num, k] = ways
		return ways

	def numberSequence(self, m, k):
		self.tb = {}
		res = 0
		start = 1
		while start << k - 1 <= m:
			res += self.recursive_thinking(m, start, 1, k)
			start += 1
		return res

	def recursive_thinking(self, A, curr, number_of_ele, k):
		rem = k - number_of_ele
		if curr << rem > A:
			return 0
		if rem == 0:
			return 1
		if (curr, number_of_ele) in self.tb:
			return self.tb[curr, number_of_ele]
		start = 2 * curr
		ans = 0
		while start <= A:
			if start << rem - 1 > A:
				break
			ans += self.recursive_thinking(A, start, number_of_ele + 1, k)
			start += 1
		self.tb[curr, number_of_ele] = ans
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def f(self, num, k):
		if num < k:
			return 0
		if k == 0:
			return 1
		if (num, k) in self.tb:
			return self.tb[num, k]
		ways = self.f(num // 2, k - 1) + self.f(num - 1, k)
		self.tb[num, k] = ways
		return ways

	def numberSequence(self, m, n):
		self.tb = {}
		return self.f(m, n)


class Solution:

	def numberSequence(self, max_val, req):
		dp = [[None for j in range(req + 1)] for i in range(max_val + 1)]

		def dfs(cur, size):
			if size == 0 and cur > 0:
				return 1
			if cur <= 0 or size == 0:
				return 0
			if dp[cur][size] != None:
				return dp[cur][size]
			val = 0
			for i in range(cur // 2, 0, -1):
				ret_val = dfs(i, size - 1)
				if not ret_val:
					break
				val += ret_val
			dp[cur][size] = val
			return dp[cur][size]
		res = 0
		for i in range(max_val, 0, -1):
			res += dfs(i, req - 1)
		return res


class Solution:

	def numberSequence(self, m, n):
		T = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					T[i][j] = 0
				elif i < j:
					T[i][j] = 0
				elif j == 1:
					T[i][j] = i
				else:
					T[i][j] = T[i - 1][j] + T[i // 2][j - 1]
		return T[m][n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		m = int(arr[0])
		n = int(arr[1])
		ob = Solution()
		print(ob.numberSequence(m, n))


from functools import lru_cache

class Solution:

	def numberSequence(self, m, n):

		@lru_cache()
		def help(i, c):
			ans = 0
			if c >= n:
				return 1
			if i > m:
				return 0
			ans += help(2 * i, c + 1)
			ans += help(i + 1, c)
			return ans
		return help(1, 0)


class Solution:

	def getRes(self, dp, n, m, start):
		if n == 0:
			return 1
		elif start > m:
			return 0
		elif dp[n][start] != -1:
			return dp[n][start]
		else:
			res = 0
			for i in range(start, m + 1):
				res += self.getRes(dp, n - 1, m, 2 * i)
			dp[n][start] = res
			return res

	def numberSequence(self, m, n):
		dp = [[-1 for _ in range(109)] for _ in range(109)]
		return self.getRes(dp, n, m, 1)


class Solution:

	def numberSequence(self, m, n):
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if i == 1:
					dp[i][j] = j
				elif i > j:
					dp[i][j] = 0
				else:
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j // 2]
		return dp[n][m]