• Leetcode POTDs

Problem 3133 Minimum Array End

Problem Statement

Link - Problem 3133

Question

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

Solution

class Solution {
public:
    long long minEnd(int n, int x) {

        long long res = x;
        n=n-1;
        while(n--){
            res = (res+1)|x;
        }
        return res;
    }
};

Complexity Analysis

| Algorithm                  | Time Complexity | Space Complexity |
| -------------------------- | --------------- | ---------------- |
| Bit-manipulation traversal | O(n)            | O(1)             |

Explanation

1. Intuition

• The problem requires constructing an array of positive integers where each element is greater than the previous one, and the bitwise AND of all elements is x.
• To minimize the last element of the array, we should start with x and increment it by the smallest possible amount in each step.
• Since the bitwise AND of all elements must be x, we can’t change the bits that are set in x.
• The key insight is to use the bitwise OR operation to set the bits that are not set in x, which allows us to increment the number while keeping the bitwise AND unchanged.
• This approach works because the bitwise OR operation sets a bit to 1 if either of the corresponding bits in the operands is 1.
• By using the bitwise OR operation with x, we ensure that the bitwise AND of all elements remains x.
• This solution has a time complexity of O(n) because we perform a constant amount of work in each iteration of the while loop.

2. Implementation

• The function minEnd takes two integers n and x as input and returns the minimum possible value of the last element in the array.
• We initialize the result res to x and decrement n by 1 because we don’t need to consider the first element separately.
• The while loop iterates n times, and in each iteration, we update res to be the bitwise OR of res + 1 and x using the expression (res+1)|x.
• This expression sets the bits in res that are not set in x to 1, effectively incrementing res by the smallest possible amount.
• After the loop, res contains the minimum possible value of the last element in the array, which we return as the result.

Complexity Analysis

Time Complexity:

• The loop while(n--) executes n times, which directly influences the time complexity.
• Within the loop, the operations res = (res+1)|x perform constant-time bit manipulation and addition.
• Since the loop executes n times, the overall time complexity is linear, classified as O(n). In both worst-case and best-case scenarios, the loop executes n times.

Space Complexity:

• The algorithm only uses a constant amount of space, storing variables res, n, and x in memory.
• The loop does not create any data structures that grow with the input size n.
• As a result, the space complexity is constant, classified as O(1), regardless of the input size n.

Footnote

This question is rated as Medium difficulty.

Hints

Each element of the array should be obtained by “merging” x and v where v = 0, 1, 2, …(n - 1).

To merge x with another number v, keep the set bits of x untouched, for all the other bits, fill the set bits of v from right to left in order one by one.

So the final answer is the “merge” of x and n - 1.