ধরুন আমাদের 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
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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 }
আউটপুট
3