3133. Minimum Array End

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:

Example 2:

Constraints:

• 1 <= n, x <= 108

Approach 01:

class Solution {
public:
    long long minEnd(int numBits, int inputNum) {
        // Calculate maximum bits needed based on the inputs
        const int maxBits = log2(numBits) + log2(inputNum) + 2;
        const long targetValue = numBits - 1;
        long resultNum = inputNum;
        int bitIndex = 0;

        // Iterate through each bit up to maxBits
        for (int i = 0; i < maxBits; ++i) {
            // Check if the current bit of resultNum is 0
            if ((resultNum >> i & 1) == 0) {
                // If the corresponding bit in targetValue is 1, set it in resultNum
                if (targetValue >> bitIndex & 1)
                    resultNum |= 1L << i;
                ++bitIndex;
            }
        }

        return resultNum;
    }
};

class Solution:
    def minEnd(self, numBits, inputNum):
        # Calculate maximum bits needed based on the inputs
        maxBits = int(log2(numBits) + log2(inputNum) + 2)
        targetValue = numBits - 1
        resultNum = inputNum
        bitIndex = 0

        # Iterate through each bit up to maxBits
        for i in range(maxBits):
            # Check if the current bit of resultNum is 0
            if (resultNum >> i & 1) == 0:
                # If the corresponding bit in targetValue is 1, set it in resultNum
                if (targetValue >> bitIndex & 1):
                    resultNum |= 1 << i
                bitIndex += 1

        return resultNum

Time Complexity

• Calculating maxBits:

  The calculation of maxBits using logarithmic operations takes \( O(1) \) time since it only involves a few mathematical operations.

• Iterating through Bits:

  The main loop runs up to maxBits times. In the worst case, this would be proportional to the number of bits required to represent the inputs, resulting in \( O(\log_2(\text{numBits}) + \log_2(\text{inputNum})) \).

• Bitwise Operations:

  Each iteration involves a few bitwise operations, which are constant time operations \( O(1) \). Thus, the total complexity is dominated by the loop.

• Overall Time Complexity:

  The overall time complexity is \( O(\log_2(\text{numBits}) + \log_2(\text{inputNum})) \).

Space Complexity

• Auxiliary Variables:

  The function uses a few variables like resultNum, targetValue, and bitIndex, which take up constant space \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \) as no additional data structures are used, and the space usage does not depend on the size of the inputs.