leetcode/solution/3100-3199/3133.Minimum Array End

comments	difficulty	edit_url	rating	source	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3133.Minimum%20Array%20End/README_EN.md	1934	Weekly Contest 395 Q3	Bit Manipulation

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).

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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);
}