Problem

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

Examples

Example 1:

1
2
3

Input: n = 3, x = 4
Output: 6
Explanation: `nums` can be `[4,5,6]` and its last element is 6.

Example 2:

1
2
3

Input: n = 2, x = 7
Output: 15
Explanation: `nums` can be `[7,15]` and its last element is 15.

Solution

Method 1 - Bit manipulation using OR

The smallest element equals x, and all elements look like x with some additional bits. So, initially, num can be equal to x, and then each time we increment num by 1, and apply bitwise OR with x, we will get next valid bigger element.

And we have to repeat above operation n - 1 times (as x is already the first element) , to get our ans.

Code

1
2
3
4
5
6
7
8
9

class Solution {
    public long minEnd(int n, int x) {
        long num = x;
        while (--n > 0) {
            num = (num + 1) | x;
        }
        return num;
    }
}
1
2
3
4
5
6
7

class Solution:
    def min_end(self, n: int, x: int) -> int:
        num = x
        while n > 1:
            num = (num + 1) | x
            n -= 1
        return num

Complexity

  • ⏰ Time complexity: O(n), as the loop runs n - 1 times
  • 🧺 Space complexity: O(1), as we only use a few extra variables.

Method 2 - Bit interweaving

The key idea is to utilize the bits of n-1 and strategically place them into the positions where x has zero bits. Lets take number 22 = 10110, and let n = 4.

As x is already the first number, we just need n - 1 numbers, i.e. 3.

So, we can decrement from n to 1 like in previous approach, and interweave it around the existing bits in x.

The elements, smallest to largest, starting from x, will look like:

  • 10110
  • 10111
  • 11110
  • 11111
  • .. and so on

$$ x_0 = \begin{array}{|c|c|c|c|c|} \hline \colorbox{lightgreen}{1} & {0} & \colorbox{lightgreen}{1} & \colorbox{lightgreen}{1} & 0 \\ \hline \end{array} $$ $$ x_1 = \begin{array}{|c|c|c|c|c|} \hline \colorbox{lightgreen}{1} & {0} & \colorbox{lightgreen}{1} & \colorbox{lightgreen}{1} & \colorbox{orange}{1} \\ \hline \end{array} $$ $$ x_2 = \begin{array}{|c|c|c|c|c|} \hline \colorbox{lightgreen}{1} & \colorbox{orange}{1} & \colorbox{lightgreen}{1} & \colorbox{lightgreen}{1} & 0 \\ \hline \end{array} $$ $$ x_3 = \begin{array}{|c|c|c|c|c|} \hline \colorbox{lightgreen}{1} & \colorbox{orange}{1} & \colorbox{lightgreen}{1} & \colorbox{lightgreen}{1} & \colorbox{orange}{1} \\ \hline \end{array} $$ And so on….

Approach

  1. Initialization:
    • We decrement n by 1 (n = n - 1) because x is already considered as the first element of our array, so we only need to find the other n-1 elements.
  2. Bit Manipulation:
    • We use a bit variable b which is initially set to 1 and keep shifting it left (b <<= 1) in each iteration to explore each bit position.
  3. Decision Making:
    • For each bit position b, we check if it is an empty bit in x by comparing b & x with 0.
      • If (b & x) == 0 (i.e., the bit is not set in x), we have two choices:
        • Leave it empty.
        • Fill it.
      • By iterating through all possible empty bits, we can find the smallest possible number that satisfies the condition.
  4. Setting Bits:
    • If the first bit of n (i.e., n & 1) is on, we turn on the corresponding bit in a by a |= (n & 1) * b.
    • Right-shift n by 1 (n >>= 1) to process the next bit.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public long minEnd(int n, int x) {
        long num = x;
        for (long b = 1; n > 1; b <<= 1) {
            if ((b & x) == 0) {  // Check for empty bit in x
                num |= (n & 1) * b;  // Set the b-th bit if the 1st bit of n is on
                n >>= 1;  // Right shift n to process the next bit
            }
        }
        return num;  // Return the minimum possible value of the last element
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def min_end(self, n: int, x: int) -> int:
        n -= 1  # Use n - 1 because x is already considered as the first element
        num = x
        b = 1
        while n > 0:
            if (b & x) == 0:  # Check for empty bit in x
                num |= (n & 1) * b  # Set the b-th bit if the 1st bit of n is on
                n >>= 1  # Right shift n to process the next bit
            b <<= 1  # Shift b to the next bit position
        return num  # Return the minimum possible value of the last element

Complexity

  • ⏰ Time complexity: O(70)
    • Even with a large value for n, the number of necessary iterations is limited by the bits in the final number.
    • For example, 10^8 ≈ 2^26 implies 2^26 as the starting value for x.
    • With n set to 10^8, the maximum bits in the final number cannot exceed 26 + 27 = 53.
  • 🧺 Space complexity: O(1)