C++でNを除算する際の商よりも多くのセットビットを持つ除数の数

整数が与えられます。たとえば、除数と見なされるNは、1-Nから始まる数で除算されます。タスクは、より多くのセットビット数を持つ除数の数を計算することです。与えられた数Nで割ったときの商。

例

入力- int N =6

出力- Nを除算する際の商よりも多くのセットビットを持つ除数の数は次のとおりです。5

説明- まず、数値Nを1-Nから始まる数値で除算し、除数と商のセットビットを計算します。

1-> N =6/1（1）=6（2）=1<2=考慮されない

2-> N =6/2（1）=3（2）=2 =2=考慮される

3-> N =6/3（2）=2（1）=2>1=考慮される

4-> N =6/4（1）=1（1）=1 =1=考慮される

5-> N =6/5（2）=1（1）=2>1=考慮される

6-> N =6/6（2）=1（1）=2>1=考慮される

ご覧のとおり、検討したケースを取り上げ、出力は5になります。

入力- int N =10

出力- Nを除算する際の商よりも多くのセットビットを持つ除数の数は次のとおりです。8

説明- まず、数値Nを1-Nから始まる数値で除算し、除数と商のセットビットを計算します。

1-> N =10/1（1）=10（2）=1<2=考慮されない

2-> N =10/2（1）=5（2）=2 =2=考慮される

3-> N =10/3（2）=3（2）=2 =2=考慮される

4-> N =10/4（1）=2（1）=1<2=考慮されない

5-> N =10/5（2）=2（1）=2>2=考慮される

6-> N =10/6（2）=1（1）=2>1=考慮される

7-> N =10/7（3）=1（1）=3>1=考慮される

8-> N =10/8（1）=1（1）=1 =1=考慮される

9-> N =10/9（2）=1（1）=2>2=考慮される

10-> N =10/10（2）=1（1）=2>1=考慮される

ご覧のとおり、検討したケースを取り上げ、出力は8になります。

以下のプログラムで使用されているアプローチは次のとおりです

• 正の整数Nを入力し、引数として関数divisors_quotient（）に渡します。
• 関数divisors_quotient（）
  内
  • N-呼び出しを関数set_quo（N）+ 1に戻し、関数set_quo（）に移動します
• 関数set_quo（）の内部
  • startとendとして一時変数を作成し、startを1で初期化し、endをsqrt（N）で初期化します。
  • 開始<終了までループを開始し、一時変数をtempとして作成し、（開始+終了）/2に設定します
  • IFをチェックし（関数verify（）を呼び出し、引数としてtempとNを渡します）、endをtempとして設定します
  • それ以外の場合は、開始をtemp+1に設定します
  • IF（！関数verify（）を呼び出し、引数としてtempとNを渡す）、start+1を返します。
  • それ以外の場合は、スタートを返します
• 関数verify（）内
  • IF（関数val_bit（temp / val）の呼び出しが関数val_bit（val）の呼び出しよりも小さい）を確認してからtrueを返し、それ以外の場合はFalseを返します
• 関数val_bit（）の内部
  • 結果を格納するための一時変数カウントを宣言します。
  • valに値があるときにループを開始します。ループ内で、valをval / 2に設定し、カウントを1増やします。
  • リターンカウント。

例

#include <bits/stdc++.h>
using namespace std;

int val_bit(int val) {
   int count = 0;
   while (val) {
      val = val / 2;
      count++;
   }
   return count;
}
bool verify(int val, int temp) {
   if (val_bit(temp / val) <= val_bit(val)) {
      return true;
   }
   return false;
}
int set_quo(int N) {
   int start = 1;
   int end = sqrt(N);
   while (start < end) {
      int temp = (start + end) / 2;
      if (verify(temp, N)) {
         end = temp;
      } else {
         start = temp + 1;
      }
   }
   if (!verify(start, N)) {
      return start + 1;
   } else {
      return start;
   }
}

int divisors_quotient(int N) {
   return N - set_quo(N) + 1;
}
int main() {
   int N = 10;
   cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N);
   return 0;
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of divisors having more set bits than quotient on dividing N are: 8