หาตัวเลขจากตัวหารของมันด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ divisors[] ที่เป็นตัวหารของตัวเลข Num (ไม่รวม 1 และ Num เอง) ต้องหาตัวเลข Num

ตัวอย่าง

อินพุต

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

เอาต์พุต

75

คำอธิบาย

ตัวเลข 75 มีตัวหาร (ไม่รวม 1, 75) คือ {3, 5, 15, 25}

วิธีแก้ปัญหา

ข้อสังเกต: ตัวเลข Num = ตัวหารน้อยที่สุด × ตัวหารมากที่สุด

1. เรียงอาร์เรย์ divisors
2. Num = divisors[0] × divisors[n-1]
3. หาตัวหารทั้งหมดของ Num (ไม่รวม 1, Num)
4. เปรียบเทียบกับ divisors[] เดิม ถ้าตรงกัน return Num ไม่เช่นนั้น return -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];
    
    // หาตัวหารทั้งหมดของ num (ไม่รวม 1 และ num)
    vector<int> numDiv;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            numDiv.push_back(i);
            if (i != num / i)
                numDiv.push_back(num / i);
        }
    }
    sort(numDiv.begin(), numDiv.end());
    
    // ตรวจสอบ
    if (numDiv.size() != n)
        return -1;
    for (int i = 0; i < n; 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

สรุป

ใช้คุณสมบัติ: ตัวหารน้อยที่สุด × ตัวหารมากที่สุด = ตัวเลขเดิม ตรวจสอบความถูกต้องโดยหาตัวหารทั้งหมด