โค้ด C++ นับจำนวนสีขั้นต่ำในการระบายสีอาร์เรย์

สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ เราต้องระบายสีองค์ประกอบให้:

ถ้าพิจารณาสีใดสีหนึ่ง ทุกองค์ประกอบของสีนั้นต้องหารด้วยองค์ประกอบน้อยสุดของสีเดียวกันลงตัว
จำนวนสีที่ใช้ควรน้อยที่สุด

เราต้องหาจำนวนสีขั้นต่ำในการระบายสีตัวเลขทั้งหมดอย่างถูกต้อง

เช่น ถ้าอินพุตคือ A = [10, 2, 3, 5, 4, 2] เอาต์พุตจะเป็น 3

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
ans := 0
เรียงลำดับอาร์เรย์ A
for i := 0 ถึง n-1:
    ok := 1
    for j := 0 ถึง i-1:
        ok := ok AND (1 ถ้า A[i] mod A[j] != 0 มิฉะนั้น 0)
    ans := ans + ok
return ans

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

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

int solve(vector<int> A) {
    int n = A.size();
    int ans = 0;
    sort(A.begin(), A.end());
    for (int i = 0; i < n; i++) {
        int ok = 1;
        for (int j = 0; j < i; j++)
            ok &= (A[i] % A[j] != 0);
        ans += ok;
    }
    return ans;
}

int main() {
    vector<int> A = { 10, 2, 3, 5, 4, 2 };
    cout << solve(A) << endl;
}

อินพุต

{ 10, 2, 3, 5, 4, 2 }