मान लीजिए हमारे पास n तत्वों की एक सरणी A है। हमें तत्वों को रंगों में रंगना है जैसे कि:
यदि हम किसी भी रंग पर विचार करते हैं, तो इस रंग के सभी तत्व उसी रंग के न्यूनतम तत्व से विभाज्य होने चाहिए।
उपयोग किए गए रंगों की संख्या न्यूनतम होनी चाहिए।
हमें दी गई सभी संख्याओं को वैध तरीके से रंगने के लिए न्यूनतम रंगों की संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट 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
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(vector 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 A = { 10, 2, 3, 5, 4, 2 }; cout << solve(A) << endl; }
इनपुट
{ 10, 2, 3, 5, 4, 2 }आउटपुट
3
