3133. Minimum Array End

NeetCode: Minimum Array End · LeetCode: 3133. Minimum Array End · Difficulty: Medium

Given two integers n and x, construct a strictly increasing array nums of n positive integers such that the bitwise AND of all its elements equals x. Return the minimum possible value of nums[n - 1].

Example

Input:  n = 3, x = 4    Output: 6     (nums = [4, 5, 6])
Input:  n = 2, x = 7    Output: 15    (nums = [7, 15])

Brute force: scan upward

For the AND to equal x, every element must contain all the bits of x (be a "superset" of x), that is, (v & x) == x. In Java, == binds tighter than &, so the parentheses are required. The smallest such number is x itself, and taking the n smallest supersets keeps x in the array, so their AND is exactly x and the last element is as small as it can be. Therefore: start at x, count upward, and count only the numbers with (v & x) == x; the n-th one is the answer.

This is correct but slow: only about one number in 2^popcount(x) is a superset, so the scan takes around n · 2^popcount(x) steps.

public class Main {
    static class Solution {
        public long minEnd(int n, int x) {
            long v = x;
            long count = 1; // x itself is the first element
            while (count < n) {
                v++;
                if ((v & x) == x) {
                    count++;
                }
            }
            return v;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minEnd(3, 4));
        System.out.println(s.minEnd(2, 7));
        System.out.println(s.minEnd(1, 9));
        System.out.println(s.minEnd(5, 1));
    }
}

6
15
9
9

Time: O(n · 2^popcount(x)) (the value of the answer). Space: O(1).

Optimal: deposit the bits of n - 1 into the zero bits of x

The supersets of x are made by choosing any values for the bit positions where x has a 0; the positions where x has a 1 are fixed. Listing supersets in increasing order is therefore counting in binary using only those free positions. The n-th superset (0-indexed: n - 1) is obtained by writing n - 1 in binary and spreading its bits, lowest first, into the zero bits of x.

Example n = 3, x = 4 (100): n - 1 = 2 = 10. The zero bits of x are positions 0, 1, 3, ...; put the low bit of n-1 (0) at position 0 and the next bit (1) at position 1, giving 100 | 010 = 110 = 6.

Walk over the bit positions of x; at each zero bit, place the next bit of n - 1. Stop when all bits are placed. The method returns long because the answer can exceed 32 bits. In x & bit, the int x is widened to long first, so the comparison is exact.

public class Main {
    static class Solution {
        public long minEnd(int n, int x) {
            long remaining = n - 1L; // n >= 1
            long result = x;
            long bit = 1L;
            while (remaining > 0) {
                if ((x & bit) == 0) {
                    if ((remaining & 1) == 1) {
                        result |= bit;
                    }
                    remaining >>= 1;
                }
                bit <<= 1;
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minEnd(3, 4));
        System.out.println(s.minEnd(2, 7));
        System.out.println(s.minEnd(1, 9));
        System.out.println(s.minEnd(5, 1));
        System.out.println(s.minEnd(100_000_000, 100_000_000));
    }
}

6
15
9
9
409632367103

Time: O(log x + log n). Space: O(1).

The loop always ends: above the highest set bit of x every position is free, so the remaining bits of n - 1 get consumed, and bit stays far below 63 bits for n, x <= 10^8. The constraint n >= 1 makes n - 1 non-negative, and n - 1L is computed in long, so it cannot overflow.