問題文

2つの整数 n と x が与えられます。長さ n の正の整数配列 nums を構築する必要があります。すべての 0 <= i < n - 1 について、nums[i + 1] が nums[i] より大きく、かつ配列 nums のすべての要素のビット単位のAND演算結果が x となるようにしてください。

nums[n - 1] の考えられる最小値を返してください。

例1：

入力： n = 3, x = 4

出力： 6

説明：

配列 nums は [4,5,6] とすることができます。最後の要素は6です。

例2：

入力： n = 2, x = 7

出力： 15

説明：

配列 nums は [7,15] とすることができます。最後の要素は15です。

解法：ビット演算と双ポインタ

考え方

すべてのnumのAND演算結果がxになるということは、xのビット表現で1となっているビット位置は、すべてのnumでも1である必要があります。

では、その他の位置（xのビット表現で0の位置）はどうでしょうか？もちろん0でも1でも構いません。

配列numsの中で最大の数をできるだけ小さくするため、xの0の位置に0からn-1までの二進数を埋め込むのが最適です。

結論：xの0の位置にn-1の二進数を埋め込むことで、最適な配列を構築できます。

具体的な手順

1 ≤ n ≤ 10^8 ≤ 2^27であるため、n-1の下位27ビットだけを考慮すれば十分です。

2つのポインタを使用します。一つはxの各ビットを指し、もう一つはnの各ビットを指します。

主ループでは、inを0から26まで（nの各ビットを指す）動かし、xの0の位置を見つけてnの対応するビット値を埋め込みます。

• xのixビットを取り出す：(x >> ix) & 1
• nのinビットを取り出す：(n >> in) & 1
• inビットをnのinビットに設定する：x |= (((n >> in) & 1) << ix)

計算量の分析

• 時間計算量：O(C)、ここでC = log(max{n, x}) = 27
• 空間計算量：O(1)

実装コード

C++

/*
xの各0の位置にn-1のビットを埋め込む
*/
typedef long long ll;

class Solution {
public:
    ll minEnd(ll n, ll x) {
        n--;
        int in = 0, ix = 0;
        while (in < 27) {
            // xの次の0のビット位置を見つける
            while ((x >> ix) & 1) {
                ix++;
            }
            // nのinビットをxのixビット位置に設定
            if ((n >> in) & 1) {
                x |= (1LL << ix);
            }
            in++;
            ix++;
        }
        return x;
    }
};

Go

package main

func minEnd(n int, x int) int64 {
    n64, ans := int64(n-1), int64(x)
    in, ix := 0, 0
    
    for in < 27 {
        // xの次の0のビット位置を見つける
        for (ans >> ix) & 1 == 1 {
            ix++
        }
        // nのinビットをansのixビット位置に設定
        if (n64 >> in) & 1 == 1 {
            ans |= (1 << ix)
        }
        in++
        ix++
    }
    return ans
}

Java

class Solution {
    public long minEnd(long n, long x) {
        n--;
        int in = 0, ix = 0;
        
        while (in < 27) {
            // xの次の0のビット位置を見つける
            while (((x >> ix) & 1) == 1) {
                ix++;
            }
            // nのinビットをxのixビット位置に設定
            if (((n >> in) & 1) == 1) {
                x |= (1L << ix);
            }
            in++;
            ix++;
        }
        return x;
    }
}

Python

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n -= 1
        ix = 0
        result = x
        
        for in_ in range(27):
            # resultの次の0のビット位置を見つける
            while (result >> ix) & 1:
                ix += 1
            # nのin_ビットをresultのixビット位置に設定
            if (n >> in_) & 1:
                result |= (1 << ix)
            ix += 1
        return result