Skip to content

3133. Minimum Array End

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

Solutions

Solution 1: Greedy + Bit Manipulation

According to the problem description, to make the last element of the array as small as possible and the bitwise AND result of the elements in the array is $x$, the first element of the array must be $x$.

Assume the binary representation of $x$ is $\underline{1}00\underline{1}00$, then the array sequence is $\underline{1}00\underline{1}00$, $\underline{1}00\underline{1}01$, $\underline{1}00\underline{1}10$, $\underline{1}00\underline{1}11$...

If we ignore the underlined part, then the array sequence is $0000$, $0001$, $0010$, $0011$..., the first item is $0$, then the $n$-th item is $n-1$.

Therefore, the answer is to fill each bit of the binary of $n-1$ into the $0$ bit of the binary of $x$ based on $x$.

The time complexity is $O(\log x)$, and the space complexity is $O(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n -= 1
        ans = x
        for i in range(31):
            if x >> i & 1 ^ 1:
                ans |= (n & 1) << i
                n >>= 1
        ans |= n << 31
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public long minEnd(int n, int x) {
        --n;
        long ans = x;
        for (int i = 0; i < 31; ++i) {
            if ((x >> i & 1) == 0) {
                ans |= (n & 1) << i;
                n >>= 1;
            }
        }
        ans |= (long) n << 31;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    long long minEnd(int n, int x) {
        --n;
        long long ans = x;
        for (int i = 0; i < 31; ++i) {
            if (x >> i & 1 ^ 1) {
                ans |= (n & 1) << i;
                n >>= 1;
            }
        }
        ans |= (1LL * n) << 31;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func minEnd(n int, x int) (ans int64) {
    n--
    ans = int64(x)
    for i := 0; i < 31; i++ {
        if x>>i&1 == 0 {
            ans |= int64((n & 1) << i)
            n >>= 1
        }
    }
    ans |= int64(n) << 31
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function minEnd(n: number, x: number): number {
    --n;
    let ans: bigint = BigInt(x);
    for (let i = 0; i < 31; ++i) {
        if (((x >> i) & 1) ^ 1) {
            ans |= BigInt(n & 1) << BigInt(i);
            n >>= 1;
        }
    }
    ans |= BigInt(n) << BigInt(31);
    return Number(ans);
}

Comments