C++で除数から数を見つける

この問題では、数Numの約数であるN個の整数で構成される配列divisors[]が与えられます。私たちの仕事は、除数から数を見つけることです。

除数配列には1と数値は含まれていません。

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

入力

divisors[] = {3, 25, 5, 15}

出力

75

説明

The number 75 has divisors {3, 25, 5, 15}

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

この問題を解決するには、数の最小と最大の約数を使用して数Numを見つける必要があります。

Num = smallest * largest

このためには、配列の除数[]を並べ替えてから、配列の最初と最後のインデックスにある要素の積を見つける必要があります。

数Numについては、数のすべての因子を見つけます。そして、その数の約数が除数配列と同じであることを確認してください。はいの場合、Numを返します。それ以外の場合は、-1を返し、番号が見つからないことを示します。

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

例

#include <bits/stdc++.h>
using namespace std;
int findNumberFromDiv(int divisors[], int n){
   sort(divisors, divisors + n);
   int num = divisors[0] * divisors[n - 1];
   int numDiv[2*n];
   int count = 0;
   for (int i = 2; i * i <= num; i++){
      if (num % i == 0){
         numDiv[count] = i;
         count ++ ;
         numDiv[count] = num/i;
         count++;
      }
   }
   sort(numDiv, numDiv + count);
   if (count != n)
      return -1;
   else{
      for (int i = 0; i < count; i++) {
         if (divisors[i] != numDiv[i])
            return -1;
      }
   }
   return num;
}
int main(){
   int divisors[] = { 3, 25, 5, 15 };
   int n = sizeof(divisors) / sizeof(divisors[0]);
   cout<<"The number is "<<findNumberFromDiv(divisors,n);
   return 0;
}

出力

The number is 75