รหัส C ++ เพื่อนับสีเพื่อระบายสีองค์ประกอบอย่างถูกต้อง

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n เราจำเป็นต้องทาสีองค์ประกอบด้วยสีที่ −

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

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

ดังนั้น หากอินพุตเป็นเหมือน A =[10, 2, 3, 5, 4, 2] ผลลัพธ์จะเป็น 3 เพราะทาสีแรกให้กับองค์ประกอบ A[0] และ A[3] ให้ระบายสีสีที่สอง ไปที่องค์ประกอบ A[2] และระบายสีที่สามให้กับองค์ประกอบทั้งสามที่เหลือ

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

n := size of A
ans := 0
sort the array A
for initialize i := 0, when i < n, update (increase i by 1), do:
   ok := 1
   for initialize j := 0, when j < i, update (increase j by 1),
do:
      ok := ok AND (1 if A[i] mod A[j] is not 0, otherwise 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 }