Akku likes binary numbers and she likes playing with these numbers. Her teacher once gave her a question.For given value of  L and R, Akku have to find the count of number X, which have only three-set bits in it's binary representation such that "L ≤ X ≤ R".Akku is genius, she solved the problem easily. Can you do it ??
Example 1:
Input:
L = 11 and R = 19 
Output: 4
Explanation:
There are 4 such numbers with 3 set bits in 
range 11 to 19.
11 -> 1011
13 -> 1101
14 -> 1110
19 -> 10011
 
Example 2:
Input:
L = 25 and R = 29
Output: 3
Explanation:
There are 3 such numbers with 3 set bits in
range 25 to 29. 
25 -> 11001 
26 -> 11010 
28 -> 11100
Your Task:  
You don't need to read input or print anything. Your task is to complete the function solve() which takes the integer L and R as input parameters and returns the count of number X, which have only three-set bits in its binary representation such that "L ≤ X ≤ R".
Expected Time Complexity: O(63^{3}) + O(log(R-L))
Expected Auxiliary Space: O(63^{3})
Constraints:
1 ≤ L ≤ R ≤ 10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def solve (self, L, R):

        pass

        # code here

    def precompute (self):

        pass

        # code here

        



Solutions:
class Solution:

	def solve(self, L, R):
		bit_set = {}
		ans = 0
		for i in range(63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					curr = 0
					curr |= 1 << i
					curr |= 1 << j
					curr |= 1 << k
					if L <= curr <= R:
						ans += 1
		return ans

	def precompute(self):
		pass


class Solution:

	def __init__(self):
		self.tsl = self.precompute()

	def solve(self, L, R):

		def bsf(arr, k):
			n = len(arr)
			(l, h, idx) = (0, n - 1, 0)
			while l <= h:
				m = (l + h) // 2
				if arr[m] > k:
					h = m - 1
				else:
					idx = m
					l = m + 1
			return idx

		def bsc(arr, k):
			n = len(arr)
			(l, h, idx) = (0, n - 1, 0)
			while l <= h:
				m = (l + h) // 2
				if arr[m] < k:
					l = m + 1
				else:
					idx = m
					h = m - 1
			return idx
		x = bsf(self.tsl, L)
		y = bsc(self.tsl, R)
		if L not in self.tsl and R not in self.tsl:
			return y - 1 - (x + 1) + 1
		elif L not in self.tsl and R in self.tsl:
			return y - (x + 1) + 1
		elif L in self.tsl and R not in self.tsl:
			return y - 1 - x + 1
		else:
			return y - x + 1

	def precompute(self):
		ans = []
		for i in range(62):
			for j in range(i + 1, 63):
				for k in range(j + 1, 64):
					ans.append(1 << i | 1 << j | 1 << k)
		ans.sort()
		return ans


from bisect import bisect_left, bisect_right

class Solution:

	def precompute(self):
		self.arr = []
		for i in range(63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					curr = (1 << i) + (1 << j) + (1 << k)
					self.arr.append(curr)

	def solve(self, L, R):
		self.arr.sort()
		j = bisect_left(self.arr, L)
		k = bisect_right(self.arr, R)
		return k - j


from bisect import bisect_left, bisect_right

class Solution:

	def __init__(self):
		self.tbl = [(1 << i) + (1 << j) + (1 << k) for i in range(63) for j in range(i + 1, 63) for k in range(j + 1, 63)]
		self.tbl.sort()

	def solve(self, L, R):
		x = bisect_right(self.tbl, R)
		y = bisect_left(self.tbl, L)
		return x - y

	def precompute(self):
		pass


import math

class Solution:

	def solve(self, L, R):

		def find(Num):
			(ft, sc, td) = (None, None, None)
			for i in range(64, -1, -1):
				if Num & 2 ** i != 0:
					if ft is None:
						ft = i
					elif sc is None:
						sc = i
					elif td is None:
						td = i
			if ft is None:
				return 0
			count = 0
			for i in range(2, ft):
				remaining_bit_len = i
				count += self.fact2[i]
			if td is not None:
				count += td + 1
			if sc is not None and sc > 1:
				count += self.fact2[sc]
			return count
		a = find(R)
		b = find(L - 1)
		return a - b

	def precompute(self):
		self.fact2 = [1] * 64
		self.fact2[3] = 3
		for i in range(4, 64):
			self.fact2[i] = i * (i - 1) // 2


from bisect import bisect_left
from bisect import bisect_right

class Solution:
	nums = []

	def solve(self, L, R):
		low_idx = -1
		hgh_idx = -1
		low_idx = bisect_left(self.nums, L)
		hgh_idx = bisect_right(self.nums, R)
		if self.nums[hgh_idx] != R:
			hgh_idx -= 1
		return hgh_idx - low_idx + 1

	def precompute(self):
		for i in range(0, 63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					x = 2 ** k + 2 ** j + 2 ** i
					self.nums.append(x)
		tmp = set(self.nums)
		self.nums = sorted(tmp)


from math import ceil, log
from bisect import bisect_left, bisect_right

class Solution:

	def __init__(self):
		self.allPairs = []

	def precompute(self):
		for i in range(63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					num = (1 << i) + (1 << j) + (1 << k)
					self.allPairs.append(num)
		self.allPairs.sort()

	def solve(self, L, R):
		left = bisect_left(self.allPairs, L)
		right = bisect_right(self.allPairs, R) - 1
		if self.allPairs[right] > R:
			right -= 1
		return right - left + 1


from math import ceil, log

class Solution:

	def solve(self, L, R):
		maxRange = ceil(log(R, 2))
		ans = 0
		for i in range(maxRange + 1):
			for j in range(i + 1, maxRange + 1):
				for k in range(j + 1, maxRange + 1):
					num = (1 << i) + (1 << j) + (1 << k)
					if L <= num <= R:
						ans += 1
		return ans

	def precompute(self):
		pass


class Solution:

	def solve(self, L, R):
		answer = 0
		my_range = 64
		for i in range(my_range):
			for j in range(i + 1, my_range):
				for k in range(j + 1, my_range):
					tmp_answer = (1 << i) + (1 << j) + (1 << k)
					if tmp_answer >= L and tmp_answer <= R:
						answer += 1
		return answer

	def precompute(self):
		pass


from bisect import bisect_left, bisect_right

class Solution:

	def solve(self, L, R):
		low = bisect_left(self.v, L)
		high = bisect_right(self.v, R)
		return high - low

	def precompute(self):
		self.v = []
		for i in range(63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					self.v.append((1 << i) + (1 << j) + (1 << k))
		self.v.sort()


class Solution:

	def solve(self, L, R):

		def binarySearch(a, n, x):
			(l, r) = (0, n - 1)
			while l <= r:
				m = (l + r) // 2
				if a[m] == x:
					return m
				elif a[m] > x:
					r = m - 1
				else:
					l = m + 1
			return l
		a = binarySearch(self.dp, self.n, L)
		b = binarySearch(self.dp, self.n, R)
		return b - a + 1 if self.dp[b] == R else b - a

	def precompute(self):
		self.dp = []
		self.n = 0
		for i in range(62, -1, -1):
			a = 1 << i
			for j in range(i - 1, -1, -1):
				if i == j:
					continue
				b = 1 << j
				for k in range(j - 1, -1, -1):
					if j == k:
						continue
					c = 1 << k
					self.dp.append(a + b + c)
					self.n += 1
		self.dp.reverse()


class Solution:

	def solve(self, L, R):
		pass
		count = 0
		for i in range(64):
			for j in range(i + 1, 64):
				for k in range(j + 1, 64):
					binary = 0
					binary |= 1 << i
					binary |= 1 << j
					binary |= 1 << k
					if binary >= L and binary <= R:
						count += 1
		return count

	def precompute(self):
		pass


class Solution:

	def solve(self, L, R):
		ans = 0
		i = 1
		while i <= R:
			j = i * 2
			while j <= R:
				k = j * 2
				while k <= R:
					n = i | j | k
					if n >= L and n <= R:
						ans += 1
					k *= 2
				j *= 2
			i *= 2
		return ans

	def precompute(self):
		pass


from itertools import combinations
from bisect import bisect_left, bisect_right

class Solution:

	def solve(self, L, R):
		return bisect_right(self.valid, R) - bisect_left(self.valid, L)
		pass

	def precompute(self):
		self.valid = []
		for (x, y, z) in combinations(range(64), 3):
			self.valid.append((1 << x) + (1 << y) + (1 << z))
		self.valid.sort()
		pass


from itertools import combinations
from bisect import bisect_left

class Solution:

	def solve(self, L, R):
		left = bisect_left(self.three, L)
		right = bisect_left(self.three, R)
		if self.three[right] > R:
			right -= 1
		return right - left + 1

	def precompute(self):
		n = 63 * 62 * 61 // 6
		self.three = []
		for b1 in range(2, 64):
			for b2 in range(1, b1):
				for b3 in range(0, b2):
					self.three.append(2 ** b1 + 2 ** b2 + 2 ** b3)


class Solution:

	def __init__(self):
		self.allnos = []

	def solve(self, L, R):
		ans = 0
		for i in range(len(self.allnos)):
			if self.allnos[i] >= L and self.allnos[i] <= R:
				ans += 1
		return ans

	def precompute(self):
		for i in range(63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					curr = 0
					curr |= 1 << i
					curr |= 1 << j
					curr |= 1 << k
					self.allnos.append(curr)
		pass


class Solution:

	def solve(self, L, R):
		ans = 0
		tempans = 0
		pi = 1
		for i in range(65):
			tempans += pi
			pj = pi * 2
			for j in range(i + 1, 65, 1):
				tempans += pj
				pk = pj * 2
				for k in range(j + 1, 65, 1):
					if L <= tempans + pk <= R:
						ans += 1
					pk *= 2
				tempans -= pj
				pj *= 2
			tempans -= pi
			pi *= 2
		return ans

	def precompute(self):
		pass


class Solution:

	def solve(self, L, R):
		pass
		count = 0
		for i in range(63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					c = 0
					c = c | 1 << i
					c = c | 1 << j
					c = c | 1 << k
					if c >= L and c <= R:
						count += 1
		return count

	def precompute(self):
		pass


class Solution:

	def solve(self, L, R):
		a = [0] * 64
		s = 0
		c = 0
		for i in range(0, 64):
			a[i] = pow(2, i)
		for i in range(0, 64):
			for j in range(i + 1, 64):
				for k in range(j + 1, 64):
					s = a[i] + a[j] + a[k]
					if s >= L and s <= R:
						c += 1
					if s > R:
						break
		return c

	def precompute(self):
		pass


class Solution:

	def get_count(self, n):
		binary = bin(n)
		ind = 3
		count = 0
		l = len(binary)
		for i in range(l):
			if binary[i] == '1':
				count += self.dp[l - i - 1][ind]
				ind -= 1
				if ind < 1:
					count += 1
					break
		return count

	def solve(self, L, R):
		lower_bound = self.get_count(L - 1)
		upper_bound = self.get_count(R)
		return upper_bound - lower_bound

	def precompute(self):
		self.dp = [[0] * 4 for i in range(65)]
		self.dp[0][0] = 1
		for i in range(1, 65):
			self.dp[i][0] = 1
			for j in range(3, 0, -1):
				self.dp[i][j] = self.dp[i - 1][j] + self.dp[i - 1][j - 1]


class Solution:

	def solve(self, L, R):
		fcnt = 0
		for i in range(0, 64):
			for j in range(i + 1, 64):
				for k in range(j + 1, 64):
					val = 1 << i | 1 << j | 1 << k
					if val >= L and val <= R:
						fcnt += 1
		return fcnt

	def precompute(self):
		pass


class Solution:

	def __init__(self):
		self.temp = []

	def solve(self, l, r):
		count = 0
		for i in self.temp:
			if l <= i <= r:
				count += 1
		return count

	def precompute(self):
		for i in range(64):
			for j in range(i + 1, 64):
				for k in range(j + 1, 64):
					self.temp.append(2 ** i + 2 ** j + 2 ** k)
		self.temp.sort()


class Solution:

	def solve(self, L, R):
		num1 = L
		num2 = R
		bin_num1 = format(num1, 'b')
		bin_num2 = format(num2, 'b')
		Km = len(bin_num1) - 1
		Kn = len(bin_num2) - 1
		(res_num1, num1_second_pos, num1_third_pos) = self.addBinaryDigits(bin_num1)
		(res_num2, num2_second_pos, num2_third_pos) = self.addBinaryDigits(bin_num2)
		SetsFromPowerToPower = self.SetsPowerToConsecutivePower(Km, Kn)
		M = self.SetsFromPowerToNumber(res_num1, num1_second_pos, num1_third_pos, Km)
		if res_num2 == 3:
			N = self.SetsFromPowerToNumber(res_num2, num2_second_pos, num2_third_pos, Kn) + 1
		else:
			N = self.SetsFromPowerToNumber(res_num2, num2_second_pos, num2_third_pos, Kn)
		Total = SetsFromPowerToPower + N - M
		return int(Total)

	def precompute(self):
		pass

	def addBinaryDigits(self, binary):
		res = 0
		counter = 0
		second_pos = -1
		third_pos = -1
		idx = 0
		for char in binary:
			res += int(char)
			if char == '1':
				counter += 1
				if counter == 2:
					second_pos = idx
				elif counter == 3:
					third_pos = idx
			idx += 1
		return (res, len(binary) - 1 - second_pos, len(binary) - 1 - third_pos)

	def SetsFromPowerToNumber(self, DigSum, SecondPos, ThirdPos, MaxPower):
		theta_0 = 0
		theta_1 = 0
		SetsPN = 0
		if MaxPower == 0 or MaxPower == 1 or MaxPower == 2 or (DigSum == 1):
			theta_0 = 0
			theta_1 = 0
		elif DigSum == 2:
			if SecondPos == 0 or SecondPos == 1:
				theta_1 = 2
			else:
				theta_1 = SecondPos + 1
			theta_0 = 1
		elif DigSum == 3:
			theta_1 = SecondPos + 1
			theta_0 = ThirdPos + 1
		elif DigSum >= 4 and SecondPos == ThirdPos + 1:
			if MaxPower == SecondPos + 1:
				theta_1 = MaxPower
				theta_0 = theta_1
			else:
				theta_1 = SecondPos + 2
				theta_0 = 1
		else:
			theta_1 = SecondPos + 1
			theta_0 = ThirdPos + 2
		SetsPN = (theta_1 - 1) * theta_1 / 2 - (theta_1 - theta_0)
		return SetsPN

	def SetsPowerToConsecutivePower(self, MaxPower1, MaxPower2):
		SetsPP = 0
		if MaxPower1 == MaxPower2:
			True
		else:
			for i in range(MaxPower1, MaxPower2):
				SetsPP += i * (i - 1) / 2
		return SetsPP


from bisect import bisect_left, bisect_right
from math import log2, floor, factorial
from functools import reduce

class Solution:

	def __init__(self):
		self.tbl = [(1 << i) + (1 << j) + (1 << k) for i in range(63) for j in range(i + 1, 63) for k in range(j + 1, 63)]
		self.tbl.sort()

	def solve(self, L, R):
		x = bisect_right(self.tbl, R)
		y = bisect_left(self.tbl, L)
		return x - y

	def precompute(self):
		pass


class Solution:

	def solve(self, L, R):
		pass
		i = 1
		c = 0
		while i < R:
			j = i << 1
			while j < R:
				k = j << 1
				while k < R:
					tmp = i | j | k
					if L <= tmp and tmp <= R:
						c += 1
					k <<= 1
				j <<= 1
			i <<= 1
		return c

	def precompute(self):
		pass


from itertools import combinations as com

def binatodeci(binary):
	return sum((val * 2 ** idx for (idx, val) in enumerate(reversed(binary))))

def postobina(arr, n):
	res = [0 for i in range(n)]
	for ele in arr:
		res[ele] = 1
	return res

class Solution:

	def solve(self, L, R):
		br = [int(i) for i in list('{0:0b}'.format(R))]
		lisr = [i for i in range(len(br))]
		setr = list(com(lisr, 3))
		set2 = [list(setr[i]) for i in range(len(setr))]
		ans = set()
		for i in range(len(set2)):
			num = binatodeci(postobina(set2[i], len(br)))
			if num >= L and num <= R:
				ans.add(num)
		count = len(ans)
		return count

	def precompute(self):
		pass


import bisect

class Solution:

	def solve(self, L, R):
		lindex = bisect.bisect_left(self.get, L)
		rindex = bisect.bisect(self.get, R)
		return rindex - lindex

	def precompute(self):
		self.get = []
		for i in range(64, -1, -1):
			for j in range(i - 1, -1, -1):
				for k in range(j - 1, -1, -1):
					self.get.append((1 << i) + (1 << j) + (1 << k))
		self.get.sort()


class Solution:

	def solve(self, L, R):
		lb = self.to_bin(L)
		rb = self.to_bin(R)
		while len(lb) < len(rb):
			lb.append(0)
		lpos = [i for (i, x) in enumerate(lb) if x]
		rpos = [i for (i, x) in enumerate(rb) if x]
		return self.ranking(rpos, 3) - self.ranking(lpos, 3) + (len(lpos) == 3)

	def to_bin(self, x):
		bins = []
		while x > 0:
			bins.append(x % 2)
			x //= 2
		return bins

	def c(self, tol, x):
		if tol < x:
			return 0
		ans = 1
		for i in range(x):
			ans = ans * (tol - i)
		for i in range(x):
			ans = ans // (i + 1)
		return ans

	def ranking(self, pos, cnt):
		if cnt == 0:
			return 1
		if len(pos) == 0:
			return 0
		return self.c(pos[-1], cnt) + self.ranking(pos[:-1], cnt - 1)

	def precompute(self):
		pass


class Solution:

	def solve(self, L, R):
		pass
		i = 1
		count = 0
		while i < R:
			j = i << 1
			while j < R:
				k = j << 1
				while k < R:
					temp = i | j | k
					if L <= temp and temp <= R:
						count += 1
					k <<= 1
				j <<= 1
			i <<= 1
		return count

	def precompute(self):
		pass


import bisect

class Solution:

	def __init__(self):
		self.pre = []

	def solve(self, L, R):
		pass
		rv = bisect.bisect_left(self.pre, L)
		lv = bisect.bisect_right(self.pre, R)
		return lv - rv

	def precompute(self):
		for i in range(63):
			for j in range(i + 1, 63):
				for k in range(j + 1, 63):
					self.pre.append((1 << i) + (1 << j) + (1 << k))
		self.pre.sort()


class Solution:

	def solve(self, L, R):
		import math
		bits_3_set = 0
		for i in range(0, 64):
			for j in range(i + 1, 64):
				for k in range(j + 1, 64):
					s = 2 ** i + 2 ** j + 2 ** k
					if L <= s and s <= R:
						bits_3_set += 1
					elif s > R:
						break
		return bits_3_set

	def precompute(self):
		pass


class Solution:

	def linear_search(self, target):
		for i in range(len(self.valid)):
			if self.valid[i] >= target:
				return i

	def solve(self, L, R):
		n = len(self.valid)
		lower_ind = self.linear_search(L)
		higher_ind = self.linear_search(R)
		if self.valid[higher_ind] != R:
			higher_ind -= 1
		return higher_ind - lower_ind + 1

	def precompute(self):
		self.valid = set()
		for i in range(64):
			for j in range(i + 1, 64):
				for k in range(j + 1, 64):
					num = pow(2, i) + pow(2, j) + pow(2, k)
					self.valid.add(num)
		self.valid = sorted(self.valid)