C++で元の数でも割り切れる数字の並べ替えを実装する方法

整数型の数値(ここでは number と呼びます)が与えられます。この課題は、number の各桁を並べ替えて新しい数を作り、その並べ替え後の数が元の number でも割り切れるようにするというものです。

入出力シナリオの例

入力 − int number = 100035

出力 − 元の数で割り切れる並べ替え後の数値:300105

説明 − 整数 number として 100035 が与えられています。これらの桁を並べ替えて、元の数 100035 で割り切れる数を作る必要があります。桁を並べ替えた結果、100035 で割り切れる 300105 が得られました。

入力 − int number = 1000035

出力 − 元の数で割り切れる並べ替え後の数値:3000105

説明 − 整数 number として 1000035 が与えられています。同様に桁を並べ替え、1000035 で割り切れる数を探します。その結果、1000035 で割り切れる 3000105 が得られました。

入力 − int number = 28

出力 − 元の数で割り切れる並べ替え後の数値:-1

説明 − 整数 number として 28 が与えられています。桁を並べ替えると 82 になりますが、82 は 28 で割り切れません。条件を満たす並べ替えが存在しないため、出力は -1 となります。

プログラムで使用するアプローチ

• 整数型の変数(例:number)を入力として受け取り、関数 Rearrangement(number) に渡します。

• 関数 Rearrangement(number) の内部処理は以下の通りです。

  • 整数型の要素を格納する vector 変数(例:vec(10, 0))を作成します。

  • 関数 total_count(number, vec) を呼び出し、number と vec を引数として渡します。

  • i を 2 から 10 未満までループさせます。ループ内で temp を number * i に設定します。

  • 別の vector 変数(例:vec_2(10, 0))を作成します。

  • 関数 total_count(temp, vec_2) を呼び出し、temp と vec_2 を引数として渡します。

  • equal(vec.begin(), vec.end(), vec_2.begin()) が真であれば temp を返し、そうでなければ -1 を返します。

• 関数 total_count(int number, vector<int> &vec_3) の内部処理は以下の通りです。

  • number が 0 になるまで WHILE ループを回します。ループ内で vec_3[number % 10]++ として各桁の出現回数をカウントし、number を number / 10 で更新します。

このアルゴリズムのポイントは、元の数の各桁の出現回数と、number の倍数(2倍〜9倍)の各桁の出現回数を比較することです。両者の桁構成が完全に一致していれば、その倍数は「桁を並べ替えた数」として条件を満たします。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
void total_count(int number, vector<int> &vec_3){
   while(number){
      vec_3[number % 10]++;
      number = number / 10;
   }
}
int Rearrangement(int number){
   vector<int> vec(10, 0);
   total_count(number, vec);
   for(int i = 2; i < 10; i++){
      int temp = number * i;
      vector<int> vec_2(10, 0);
      total_count(temp, vec_2);
      if(equal(vec.begin(), vec.end(), vec_2.begin())){
         return temp;
      }
   }
   return -1;
}
int main(){
   int number = 100035;
   cout<<"Rearrangement of a number which is also divisible by it is: "<<Rearrangement(number);
   return 0;
}

実行結果

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

Rearrangement of a number which is also divisible by it is: 300105