Minimum Array End

Leetcode Problem:

• Minimum Array End

Summary

• Construct an array of positive integers where the result of the bitwise AND operation between all elements is given, and the array is strictly increasing.

Approach

• The approach is to create two arrays, one for the given x and one for the given n
• We then iterate through the arrays and construct the result array
• If the current bit in x is 1, we add 1 to the result array
• If the current bit in x is 0, we add the next available number from the array n
• We then calculate the final result by summing up the product of each number in the result array and its corresponding power of 2.

Complexity

• O(log n + log x) = O(log (max(n, x)))

Explanation

• The solution iterates through the arrays x and n, constructing the result array
• It uses two arrays to store the current bit in x and the next available number from n
• The time complexity is O(log (max(n, x))) because we iterate through the arrays x and n, and each iteration takes constant time
• The space complexity is also O(log (max(n, x))) because we store the result array and the two input arrays.

Solution Code:

class Solution {
public:
    vector xv, nv, ansv;
    long long minEnd(int n, int x) {
        n--;
        while(n){
            nv.push_back(n%2);
            n /= 2;
        }
        while(x){
            xv.push_back(x%2);
            x /= 2;
        }
        int nIdx = 0;
        for(int xIdx = 0; xIdx < xv.size(); xIdx++){
            if(xv[xIdx] == 1){
                ansv.push_back(1);
            } else{
                if(nIdx < nv.size()){
                    ansv.push_back(nv[nIdx++]);
                } else{
                    ansv.push_back(0);
                }
            }
        }
        while(nIdx < nv.size()){
            ansv.push_back(nv[nIdx++]);
        }
        long long ans = 0;
        long long pow = 1;
        for(int i = 0 ; i < ansv.size(); i++){
            ans += pow*ansv[i];
            pow *= 2;
        }

        return ans;
    }
};