Description
You are given two integers n
and x
. You have to construct an array of positive integers nums
of size n
where for every 0 <= i < n - 1
, nums[i + 1]
is greater than nums[i]
, and the result of the bitwise AND
operation between all elements of nums
is x
.
Return the minimum possible value of nums[n - 1]
.
Example 1:
Input: n = 3, x = 4
Output: 6
Explanation:
nums
can be [4,5,6]
and its last element is 6.
Example 2:
Input: n = 2, x = 7
Output: 15
Explanation:
nums
can be [7,15]
and its last element is 15.
Constraints:
1 <= n, x <= 108
Solution
Python3
class Solution:
def minEnd(self, n: int, x: int) -> int:
n -= 1
A = [0] * 64 # bits representation for x
B = [0] * 64 # bits representation for n - 1
for i in range(64):
A[i] = (x >> i) & 1
B[i] = (n >> i) & 1
i = 0
j = 0
while i < 64:
while i < 64 and A[i] != 0:
i += 1
A[i] = B[j]
i += 1
j += 1
ans = 0
for i in range(64):
if A[i] == 1:
ans += (1 << i)
return ans