3133. Minimum Array End

MediumBit Manipulation

Problem Description

You are given two integers n and x. The task is to construct an array of positive integers nums of size n where for each 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.

The goal is to return the smallest possible value of nums[n - 1].

Intuition

To solve this problem, we need to construct an array such that the bitwise AND of all its elements results in x, while also ensuring the array is strictly increasing.

A key insight is to start with x as the first element of the array, because x is the smallest positive number whose AND with itself is still x.

To construct the sequence, consider the binary representation of x. The elements must be greater than the previous ones, but should not alter the result of the AND operation. Hence, the subsequent elements can be viewed as increments. The idea is to use the binary representation of the count of increments (n-1) when building the sequence.

For instance, if x's binary representation has some unset bits (represented as 0s), we can allocate increments to these positions without affecting the AND. This is done by filling each unset bit in x with bits from the binary of n-1. This technique effectively minimizes the last element while ensuring all previous constraints are met. This greedy utilization of set bits within x and filling from n-1 is what leads to the optimal solution.

Solution Approach

The solution employs a greedy approach combined with bit manipulation to achieve the desired outcome. Here's how the implementation works:

Initialize the Variables:
- Start by setting ans to x, which will represent the smallest possible value of nums[n - 1].
- Adjust n as n - 1 because we are interested in the number of increments needed after the first element.
Process Each Bit:
- Iterate over the possible bit positions (from 0 to 30, assuming a 32-bit integer).
- For each bit position i, check if this bit in x is unset (0). This is done using the expression x >> i & 1 ^ 1.
- If the bit is unset, examine the corresponding bit in n using (n & 1).
- Incorporate this bit from n into ans using ans |= (n & 1) << i, thus filling unset bits of x with bits from n.
Shift Remaining Bits:
- Right-shift n by one to process the next bit in the subsequent iteration.
Handle Overflow Bits:
- After processing all bits, any remaining bits from n are shifted left by 31 positions and added to ans using ans |= n << 31. This accounts for any overflow that cannot fit in the lower bits.
Return Result:
- Finally, return the computed ans, which is the minimum possible value of nums[n - 1] that meets the conditions described.

This approach ensures that the constructed sequence maintains strict increasing order while preserving the AND result as x, thereby efficiently solving the problem with the smallest possible end element.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to understand the solution approach.

Suppose we have n = 3 and x = 2. Our goal is to create an array nums of size n such that it is strictly increasing and the bitwise AND of all elements equals x. We want the smallest possible value for nums[2].

Initialize Variables:
- Start by setting ans to x, so ans = 2. We'll set n to n - 1 = 2 to determine how many increments we need after x.
Process Each Bit:
- We will check each bit position from 0 to 30.
Bitwise Operations:
- Bit position 0: The binary of x (2) is 10. The bit at position 0 is unset (0). Check the corresponding bit in n = 2 (which is 10 in binary). The bit at position 0 in n is 0, so no change to ans for this bit.
- Bit position 1: The bit at position 1 in x is 1, so we do nothing here since we only fill unset bits.
- Bit position 2: Move to the next bit in n by dividing n by 2, so now n = 1. The bit at position 2 in x is 0. In n = 1, the bit at position 0 is 1. Thus, we set the bit at position 2 in ans using ans |= (1 << 2). This makes ans = 2 | 4 = 6.
Shift Remaining Bits:
- n is now 0 after right shifting.
Handle Overflow Bits:
- Since n is now 0, no further overflow handling is necessary.
Return Result:
- The smallest possible nums[2] is 6, which satisfies all the conditions.

Thus, the sequence nums = [2, 3, 6] satisfies the conditions: it's strictly increasing and the bitwise AND of all elements is 2.

Solution Implementation

1class Solution:
2    def minEnd(self, n: int, x: int) -> int:
3        # Decrement n by 1 to work with zero-based indexing
4        n -= 1
5        # Initialize the answer with the value of x
6        ans = x
7      
8        # Iterate over 31 bits (0 to 30) representing possible positions in a 32-bit integer
9        for i in range(31):
10            # Check if the ith bit of x is 0 (using XOR)
11            if (x >> i) & 1 == 0:
12                # Set the ith bit in ans to the corresponding bit of n
13                ans |= (n & 1) << i
14                # Right shift n by one to process the next bit
15                n >>= 1
16      
17        # Add any remaining bits in n shifted to start at the 31st bit position in ans
18        ans |= n << 31
19      
20        return ans
21

1class Solution {
2
3    public long minEnd(int n, int x) {
4        // Decrease n by 1 to use it as a bit mask in the loop
5        --n;
6      
7        // Initialize ans with the value of x
8        long ans = x;
9      
10        // Iterate for each of the first 31 bits
11        for (int i = 0; i < 31; ++i) {
12            // If the i-th bit of x is 0, perform the operation
13            if ((x >> i & 1) == 0) {
14                // Set the i-th bit of ans to the least significant bit of n
15                ans |= (n & 1) << i;
16              
17                // Right shift n to prepare for the next least significant bit
18                n >>= 1;
19            }
20        }
21      
22        // Include the remaining bits of n shifted to the left by 31
23        ans |= (long) n << 31;
24      
25        // Return the final accumulated value of ans
26        return ans;
27    }
28}
29

1class Solution {
2public:
3    long long minEnd(int n, int x) {
4        // Decrease n by 1 to account for 0-indexing
5        --n;
6        // Initialize answer with x
7        long long ans = x;
8      
9        // Iterate over the first 31 bits
10        for (int i = 0; i < 31; ++i) {
11            // Check if the i-th bit of x is 0 (use XOR with 1 to inverse the result)
12            if ((x >> i & 1) ^ 1) {
13                // Set the i-th bit of ans with the least significant bit of n
14                ans |= (n & 1) << i;
15                // Shift n to the right by 1 bit
16                n >>= 1;
17            }
18        }
19
20        // Set the 31-th bit and above in ans with the remaining bits in n
21        ans |= (1LL * n) << 31;
22
23        // Return the final result
24        return ans;
25    }
26};
27

1// This function computes a modified number from the input 'x' and 'n'
2function minEnd(n: number, x: number): number {
3    // Decrement 'n' by 1
4    --n;
5    // Initialize 'ans' as a BigInt representation of 'x'
6    let ans: bigint = BigInt(x);
7
8    // Loop over 31 bits (assuming 32-bit integer processing)
9    for (let i = 0; i < 31; ++i) {
10        // Check if the i-th bit of 'x' is 0
11        if (((x >> i) & 1) ^ 1) {
12            // Set the i-th bit of 'ans' if the least significant bit of 'n' is 1
13            ans |= BigInt(n & 1) << BigInt(i);
14            // Right shift 'n' by 1
15            n >>= 1;
16        }
17    }
18
19    // Set the bits from the 31st position onwards in 'ans'
20    ans |= BigInt(n) << BigInt(31);
21
22    // Convert 'ans' back to a number and return
23    return Number(ans);
24}
25

Time and Space Complexity

The time complexity of the code is O(\log x) because the for loop iterates over a fixed range of 31, but this range is logarithmic with respect to the operations on x, which involves bit manipulation based on the binary representation of x. Therefore, each bit is examined once.

The space complexity is O(1) because the algorithm uses a constant amount of additional space irrespective of the input size. The variables n, x, i, and ans are used to store numerical values without requiring additional data structures that grow with input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: