在 C++ 中查找下一个稀疏数!

2023-06-16 13:06:03 171

在这个问题中，我们被赋予一个整数值N。我们的任务是创建一个程序来查找下一个备件编号。

稀疏数是一种特殊类型的数，其二进制转换不包含任何相邻的1。

Example: 5(101) , 16(10000)

问题描述-对于给定的数字N，我们需要找到大于N的最小数字，这是一个稀疏数字。

让我们举个例子来理解这个问题，

输入

N = 7

输出结果

解释

8的二进制是1000，这使它成为大于n的最小稀疏数。

解决方法

该问题的一个简单解决方案是检查所有大于N的数字并停止直到找到我们的第一个稀疏数字。

为此，我们需要从N循环到无穷大，并对每个数字检查它是否是稀疏数字。如果是，则中断循环，否则继续。

程序来说明我们的解决方案的工作，

示例

#include
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<<"号码是 "<输出结果号码是 564
下一个稀疏数是 576
有效的方法
解决这个问题的一种有效方法是操纵数字的位。为此，我们将找到数字的二进制并处理发生邻接的位。从最低有效位到最高有效位，当我们同时遇到一对1时，我们将两个1都替换为0并使下一位为1。这样做直到我们到达MSB。然后将数字二进制数转换回十进制数，这就是我们的结果。
让我们在这里举个例子，
N=52
二进制数是110100
我们将从LSB开始遍历并找到二进制中的第一对连续的1。突出显示的部分是110100。然后，我们将两个1都替换为0，并在下一位添加一个1。这使得数字1000000，其二进制转换为64。
程序来说明我们的解决方案的工作，
示例
#include
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输出结果号码是 564
下一个稀疏数是 576

在 C++ 中查找下一个稀疏数!

输入

解释

解决方法

示例

有效的方法

示例

热门推荐

随机推荐