C++で次のスパース数を検索

この問題では、整数値Nが与えられます。私たちのタスクは、次のスペア番号を見つけるためのプログラムを作成することです。

スパース番号 は特殊なタイプの数値であり、その2進変換には隣接する1が含まれていません。

Example: 5(101) , 16(10000)

問題の説明 −与えられた数Nについて、スパース数であるNより大きい最小の数を見つける必要があります。

問題を理解するために例を見てみましょう

入力

N = 7

出力

8

説明

8の2進数は1000であり、nより大きい最小のスパース数になります。

ソリューションアプローチ

この問題の簡単な解決策は、Nより大きいすべての数値をチェックし、最初のスパースな数値が見つかるまで停止することです。

このために、Nから無限大にループする必要があり、各数値について、それがスパース数値であるかどうかを確認します。はいの場合はループを解除し、そうでない場合は続行します。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
bool isSpareNumber(int N){
   int currentBit = (N&1);
   int nextBit ;
   while (N!= 0){
      nextBit = currentBit;
      currentBit = (N&1);
      N >>= 1;
      if(nextBit == currentBit && nextBit == 1 && currentBit == 1)
         return false ;
   }
   return true;
}
int findNextSparseNumber(int N) {
   while(1){
      if(isSpareNumber(N))
         return N;
      N++;
   }
   return -1;
}
int main() {
   int N = 564;
   cout<<"The number is "<<N<<endl;
   cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
   return 0;
}

出力

The number is 564
The next Sparse Number is 576

効率的なアプローチ

この問題への効率的なアプローチは、数値のビットを操作することです。このために、数値の2進数を見つけて、隣接が発生するビットを操作します。最下位ビットから最上位ビットに移動し、1のペアに遭遇すると、両方の1を0に置き換えて、次のビット1を作成します。MSBに到達するまでこれを行います。次に、2進数を10進数に変換し直します。これが結果です。

ここで例を見てみましょう

N =52

数値の2進数は110100です

LSBからトラバースし、バイナリ内の連続する1の最初のペアを見つけます。 11です 0100強調表示された部分。次に、両方の1を0に置き換え、次のビットに1を追加します。これにより、数値は1000000になり、その2進変換は 64 。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
int findNextSparseNumber(int N) {
   int spNum[16];
   int n = 0;
   while (N != 0) {
      spNum[n] = (N&1);
      n++;
      N >>= 1;
   }
   n++;
   int lastCorrectedBit = 0;
   for (int i= 0 ; i< n; i++) {
      if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1){
         spNum[i+1] = 1;
         for (int j=i; j>=lastCorrectedBit; j--)
            spNum[j] = 0;
            lastCorrectedBit = i+1;
      }
   }
   int sparseNumber = 0;
   for (int i =0; i<n-1; i++)
      sparseNumber += spNum[i]*(1<<i);
   return sparseNumber;
}
int main() {
   int N = 564;
   cout<<"The number is "<<N<<endl;
   cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
   return 0;
}

出力

The number is 564
The next Sparse Number is 576