พิมพ์สมาชิกอาร์เรย์ที่หารด้วยอีกตัวหนึ่งในอาร์เรย์ลงตัวใน C++

โจทย์

ให้อาร์เรย์จำนวนเต็ม ต้องการพิมพ์เฉพาะตัวเลขที่หารด้วยอีกตัวหนึ่งในอาร์เรย์ลงตัว (อย่างน้อย 1 ตัว)

ตัวอย่าง: Input: 3 12 16 21 → Output: 12 21 (เพราะ 12 หาร 3 ลงตัว, 21 หาร 3 ลงตัว, 16 หาร 3 ไม่ลงตัว)

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

1. เก็บสมาชิกทั้งหมดใน unordered_set
2. หาค่าสูงสุดในอาร์เรย์
3. สำหรับแต่ละตัวเลข หาตัวคูณของมัน (2x, 3x...) จนถึงค่าสูงสุด ถ้าตัวคูณอยู่ใน set → ตัวคูณนั้นหารตัวเลขนี้ลงตัว
4. เก็บผลลัพธ์ใน set แยกกัน
5. จัดการกรณีตัวเลขซ้ำด้วย unordered_map นับความถี่

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void printDivisibleNumber(int arr[], int n) {
    unordered_set<int> s;
    int maxElement = INT_MIN;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
        maxElement = max(maxElement, arr[i]);
    }
    unordered_set<int> res;
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {
            for (int j = arr[i] * 2; j <= maxElement; j += arr[i]) {
                if (s.find(j) != s.end())
                    res.insert(j);
            }
        }
    }
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) mp[arr[i]]++;
    vector<int> ans;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (it->second >= 2) {
            if (res.find(it->first) == res.end()) {
                int val = it->second;
                while (val--) ans.push_back(it->first);
            }
        }
        if (res.find(it->first) != res.end()) {
            int val = it->second;
            while (val--) ans.push_back(it->first);
        }
    }
    for (auto x : ans) cout << x << "\t";
}

int main() {
    int arr[] = {2, 4, 7, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    printDivisibleNumber(arr, n);
    return 0;
}

ผลลัพธ์

12 14 4