Tìm số từ các ước của nó trong C ++

Trong bài toán này, chúng ta được đưa ra một ước số mảng [] bao gồm N số nguyên là ước của một số Num. Nhiệm vụ của chúng ta là tìm số từ các ước số của nó.

Mảng ước số không bao gồm 1 và số.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

75

Giải thích

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

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta cần tìm số Num bằng cách sử dụng ước số nhỏ nhất và lớn nhất của số đó.

Num = smallest * largest

Đối với điều này, chúng ta cần sắp xếp các ước số của mảng [] và sau đó tìm tích các phần tử ở chỉ số đầu tiên và cuối cùng của mảng.

Đối với số Num, hãy tìm tất cả các thừa số của số đó. Và kiểm tra các ước của một số có giống như trong mảng ước số không. Nếu Có, hãy trả về Num. Ngược lại, trả về -1, biểu thị số không được tìm thấy.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The number is 75