একটি অ্যারে দেওয়া আছে যেটিতে অন্য একটি অ্যারের সব সম্ভব পেয়ারের GCD মানগুলো র্যান্ডম অর্ডারে আছে। এই GCD অ্যারে থেকে মূল সংখ্যাগুলো বের করতে হবে।
উদাহরণ
GCD array: {6, 1, 1, 13}
আউটপুট: 13 6
ব্যাখ্যা: মূল সংখ্যা ১৩ ও ৬। GCD(13,13)=13, GCD(13,6)=1, GCD(6,13)=1, GCD(6,6)=6।
অ্যালগরিদম
- অ্যারেটি ডিক্রিজিং অর্ডারে সর্ট করুন।
- সর্বোচ্চ উপাদানটি অবশ্যই মূল সংখ্যা। এটি রেজাল্টে রাখুন এবং ফ্রিকোয়েন্সি কমান।
- প্রতিটি নির্বাচিত সংখ্যার সাথে ইতিমধ্যে নির্বাচিত সংখ্যাগুলোর GCD বের করে ফ্রিকোয়েন্সি থেকে ২ বিয়োগ করুন (কারণ পেয়ার অর্ডার্ড)۔
- প্রক্রিয়া চলতে দিন যতক্ষণ না পর্যাপ্ত সংখ্যা পাওয়া যায়।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
void printArr(int arr[], int n) {
for (int i=0;i 0) {
res[l] = arr[i];
freq[res[l]]--;
l++;
for (int j=0;j
আউটপুট: 13 6
