Bitwise AND
Time Limit: 1.0 s
Memory Limit: 256.0 MB
Description
You are given an array A[] and the length of the array is N. Initially, all element of the array A[] is 0.
For example , if N = 5;
Initially, array looks like, A[] = {0,0,0,0,0}.
You are also given an integer K. You can perfom following operations at most K times (possibly zero),
- In each operation select an index i from array A[], 1<=i<= N, increase it's value by 1. (Ex. A[i] = A[i] + 1).
- After perfoming each operation K is decreased by 1.
Let see, after perfoming above operation remaining K equal to \(X\), and \(Y\) = (\(A_1\) & \(A_2\) & \(A_3\) ... & \(A_N\)).
Find the maximum possible value of \(X * Y\).
Note : '&' bitwise AND operator.
Input
First line T, the number of test cases.
In each test case, two positive integers N and K.
\(1<=T<=10^5\)
\(1<=N<=10^6\)
\(1<=K<=10^9\)
Output
In each test case, print the required answers.
Sample
Input | Output |
---|---|
|
|
First test case,
N = 3, K=5;
we can perfom 3 operation on indices 1, 2, 3.
Now \(A[]\) = {1,1,1}. and \(X\) = K-3 = 5-3 = 2.
\(Y\) = (1 & 1 & 1) = 1.
\(X * Y = 2 * 1 = 2.\)
So answer is 2, which is maximum.
Information
- ID
- 1092
- Difficulty
- 8
- Category
- Implementation | Basic_Math Click to Show
- Tags
- # Submissions
- 80
- Accepted
- 12
- Accepted Ratio
- 15%
- Uploaded By
Related
In following contests: