C++의 제수에서 숫자 찾기

이 문제에서는 숫자 Num의 제수인 N개의 정수로 구성된 배열 divisors[]가 제공됩니다. 우리의 임무는 제수에서 숫자를 찾는 것입니다.

제수 배열에는 1과 숫자가 포함되지 않습니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

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

출력

75

설명

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

솔루션 접근 방식

문제를 해결하려면 숫자의 가장 작은 약수와 가장 큰 약수를 사용하여 숫자 Num을 찾아야 합니다.

Num = smallest * largest

이를 위해 배열 divisors[]를 정렬한 다음 배열의 첫 번째 및 마지막 인덱스에서 요소의 곱을 찾아야 합니다.

숫자 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