3133. Minimum Array End - Explanation

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 = 2

Output: 6

Explanation: nums can be [2,3,6].

Example 2:

Input: n = 5, x = 3

Output: 19

Explanation: nums can be [3,7,11,15,19].

Constraints:

1 <= n, x <= 100,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        res = x
        for i in range(n - 1):
            res = (res + 1) | x
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Binary Representation And Bit Manipulation

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        res = 0
        n -= 1

        x_bin = [0] * 64  # Binary representation of x
        n_bin = [0] * 64  # Binary representation of n-1

        for i in range(32):
            x_bin[i] = (x >> i) & 1
            n_bin[i] = (n >> i) & 1

        i_x = 0
        i_n = 0
        while i_x < 63:
            while i_x < 63 and x_bin[i_x] != 0:
                i_x += 1
            x_bin[i_x] = n_bin[i_n]
            i_x += 1
            i_n += 1

        for i in range(64):
            if x_bin[i] == 1:
                res += (1 << i)

        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

3. Bit Manipulation

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        res = x
        i_x = 1
        i_n = 1  # for n-1

        while i_n <= n - 1:
            if i_x & x == 0:
                if i_n & (n - 1):
                    res = res | i_x
                i_n = i_n << 1
            i_x = i_x << 1

        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$