You are given two integers N \ ( N ≥ 2) and S. You have to construct an array A containing N integers such that:
0 ≤ A_{i} ≤ S for each 1 ≤ i ≤ N
A_{1} + A_{2} + \ldots + A_{N} = S
A_{1} \mathbin{\&} A_{2} \mathbin{\&} \ldots \mathbin{\&} A_{N} = 0, where \mathbin{\&} denotes [bitwise AND] operator.
The maximum element of the array is minimized.

Find the maximum element of the array A.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two space-separated integers N and S — the length of array and sum of array elements respectively.

------ Output Format ------ 

For each test case, output on a new line the maximum element of the array A.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 10^{9}$
$1 ≤ S ≤ 10^{9}$

----- Sample Input 1 ------ 
4
2 7
3 6
5 21
100 256455

----- Sample Output 1 ------ 
4
3
5
2570

----- explanation 1 ------ 
Test case $1$: One possible array is $A = [4,3]$. Here $4 +3=7$ and $4 \mathbin{\&} 3=0$. 

Test case $2$: One possible array is $[1, 2, 3]$. Here $1+2+3=6$ and $1 \mathbin{\&} 2 \mathbin{\&} 3=0$. 

Test case $3$: One possible array is $[2, 4, 5,5,5]$. Here $2+4+5+5+5=21$ and $2 \mathbin{\&} 4 \mathbin{\&} 5 \mathbin{\&} 5 \mathbin{\&} 5=0$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Sorting

Mathematics

Complete search


Solutions:
T = int(input())
for i in range(T):
	(N, S) = map(int, input().split())
	(X, Y) = (0, S + 1)
	while X + 1 < Y:
		Mid = X + Y >> 1
		sum = 0
		count = 0
		for j in range(30, -1, -1):
			if Mid >> j & 1:
				sum += (N - 1) * (1 << j)
				count = min(count + 1, N - 1)
			else:
				sum += (1 << j) * count
		if sum >= S:
			Y = Mid
		else:
			X = Mid
	print(Y)


for _ in range(int(input())):
	(N, S) = map(int, input().split())
	(L, R) = (0, S + 1)
	while L + 1 < R:
		Mid = L + R >> 1
		s = 0
		cnt = 0
		for i in range(30, -1, -1):
			if Mid >> i & 1:
				s += (N - 1) * (1 << i)
				cnt = min(cnt + 1, N - 1)
			else:
				s += (1 << i) * cnt
		if s >= S:
			R = Mid
		else:
			L = Mid
	print(R)