C++を使用した少なくとも1つの空でないサブ配列のビットごとのANDである数値

配列が与えられ、ビット単位であり、少なくとも1つの空でないサブ配列のANDである可能性のあるすべての整数を見つける必要がある問題を解決するには、たとえば-

Input : nums[ ] = { 3, 5, 1, 2, 8 }
Output : { 2, 5, 0, 3, 8, 1 }
Explanation:
2 is the bitwise AND of subarray {2},
5 is the bitwise AND of subarray {5},
0 is the bitwise AND of subarray {1, 2}, {2, 8} and {1, 2, 8},
3 is the bitwise AND of subarray {3},
8 is the bitwise AND of subarray {8},
1 is the bitwise AND of subarray {1}, {3, 5} and {3, 5, 1}.

Input : nums[ ] = { 2, 6, 3, 8, 1 }
Output: { 1, 8, 3, 6, 2, 0 }

解決策を見つけるためのアプローチ

シンプルなアプローチ 適用できるのは、

• 空でない可能性のあるすべてのサブ配列を見つけます。

• 配列をトラバースしながら、サブ配列の各要素のビットごとのANDを計算します。

• 値の重複を避けるために、すべての結果をセットに保存してください。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] ={ 2, 6, 3, 8, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    // Declaring set to store result of each AND operation.
    unordered_set<int> result;
    int val;
    // nested loops to traverse through all the possible non empty subarrays.
    for (int i = 0; i < n; ++i){
        for (int j = i, val = INT_MAX; j < n; ++j){
            val = val & arr[j];
            // storing result of AND operation
            result.insert(val);
        }
    }
    cout << "All possible numbers are: ";
    // printing all the values of set.
    for (auto i = result.begin(); i != result.end();i++)
        cout << *i << " ";
    return 0;
}

出力

All possible numbers are: 1 8 3 6 0 2

上記のコードの説明

• AND操作のすべての結果を保存するように設定を宣言します。

• すべてのビットを1に設定してAND演算を実行する必要があるため、INT_MAXを使用して「val」変数を初期化します。

• ループ内で、i番目のインデックスから可能なすべてのサブ配列を調べます。

• 各要素のAND演算を相互に計算し、結果セットに格納します。

• 結果セットのすべての値を出力します。

結論

このチュートリアルでは、この問題を解決するための簡単なアプローチ、つまり、考えられるすべてのサブアレイでAND演算を計算する方法について説明しました。また、この問題を解決するためのC++プログラムについても説明しました。また、このコードはJava、C、Pythonなどの他の言語で記述できます。このチュートリアルがお役に立てば幸いです。