तत्वों को वैध तरीके से पेंट करने के लिए रंगों की गणना करने के लिए सी ++ कोड

मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी A है। हमें तत्वों को रंगों में इस तरह से रंगना होगा कि -

यदि हम किसी भी रंग पर विचार करते हैं, तो इस रंग के सभी तत्वों को एक ही रंग के न्यूनतम तत्व से विभाज्य होना चाहिए।
उपयोग किए गए रंगों की संख्या कम से कम होनी चाहिए।

सभी दिए गए नंबरों को वैध तरीके से रंगने के लिए हमें रंगों की न्यूनतम संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट ए =[10, 2, 3, 5, 4, 2] जैसा है, तो आउटपुट 3 होगा, क्योंकि पहले रंग को तत्वों ए [0] और ए [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 }