Skip to content

3133. Minimum Array End

SourceWeekly Contest 395 Q3DifficultyMediumRating1934

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

Thinking

Build a strictly increasing length-\(n\) array whose AND is \(x\) and whose last value is minimal. Trying the next candidate after \(x\) one by one is too slow for large \(n\).

The first value must be \(x\). Later values may only fill zeros of \(x\), otherwise the AND would lose bits. Those free bits, read as a binary counter, are exactly \(0,1,\ldots,n-1\).

Write the bits of \(n-1\) into \(x\)'s zero positions from low to high, and attach any leftover into bit \(31\) and above. The result is the minimum last element.

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