ধরুন আমাদের 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
