Given a 2D array arr[][] consisting of N*N positive integers, the task is to generate an N-length array such that Greatest Common Divisors(GCD) of all possible pairs of that array is present in the array arr[][].
Examples:
Input: N = 4, arr[] = {2, 1, 2, 3, 4, 3, 2, 6, 1, 1, 2, 2, 1, 2, 3, 2}
Output: 4, 3, 6, 2
Explanation:
Considering the array A[] as {4, 3, 6, 2}, then the GCD of all possible pairs of this array is given below which is the given array arr[].
{{4, 1, 2, 2},
{1, 3, 3, 1},
{2, 3, 6, 2},
{2, 1, 2, 2}}Input: N = 1, mat = {100}
Output: 100
Approach: The above problem can be solved by using the fact that, GCD of the largest element in the original array with itself is the largest in the arr[] and after removing the gcd pairs with that element, the next element can be found. Follow the steps below to solve the given problem:
- Initialize a map say, M store the frequency of negation of array element in the map M.
- Initialize a variable, say pos as (N – 1).
- Now, for all array elements arr[] find the maximum element.
- Traverse the map M.
- For each element of the original array, find the element with the maximum frequency and store it in the ans.
- Find ans[pos] and remove all GCD from pos+1 to N-1 of the ans.
- Update pos as pos-1.
- Repeat above steps to find all elements of the original array.
- Finally, print the ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int n;// Function to calculate GCD of two numbersint gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b);}// Function to generate an N-length// array having GCD of all pairs// present in the array mat[][]void restoreArray(vector<int> mat){ map<int, int> cnt; // Stores the required array vector<int> ans(n); for (int i = 0; i < (n * n); ++i) { // Store frequencies in map // in decreasing order cnt[-mat[i]]++; } int pos = n - 1; for (auto it = cnt.begin(); it != cnt.end(); ++it) { int x = -it->first; while (it->second) { // gcd(x, x) ans[pos] = x; --it->second; // Remove all GCDs for // indices pos + 1 -> n - 1 for (int i = pos + 1; i < n; ++i) cnt[-gcd(ans[pos], ans[i])] -= 2; // Decreasing pos pos--; } } // Print restored array for (int i = 0; i < n; ++i) printf("%d ", ans[i]);}// Driver Codeint main(){ // Given Input n = 4; vector<int> mat{ 2, 1, 2, 3, 4, 3, 2, 6, 1, 1, 2, 2, 1, 2, 3, 2 }; // Function Call restoreArray(mat); return 0;} |
Java
import java.util.*;public class GCD { static int n; // Function to calculate GCD of two numbers static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // Function to generate an N-length // array having GCD of all pairs // present in the array mat[][] static void restoreArray(ArrayList<Integer> mat) { TreeMap<Integer, Integer> cnt = new TreeMap<>(); // Stores the required array ArrayList<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; i++) ans.add(0); for (int i = 0; i < (n * n); ++i) { // Store frequencies in map // in decreasing order int x = mat.get(i); if (cnt.containsKey(-x)) { cnt.put(-x, cnt.get(-x) + 1); } else { cnt.put(-x, 1); } } int pos = n - 1; for (Map.Entry<Integer, Integer> it : cnt.entrySet()) { int x = -it.getKey(); while (it.getValue() > 0) { pos = (ans.size() + pos) % ans.size(); // gcd(x, x) ans.set(pos, x); it.setValue(it.getValue() - 1); // Remove all GCDs for // indices pos + 1 -> n - 1 for (int i = pos + 1; i < n; ++i) { int g = -gcd(ans.get(pos), ans.get(i)); if (cnt.containsKey(g)) { cnt.put(g, cnt.get(g) - 2); } } // Decreasing pos pos--; } } // Print restored array for (int i = 0; i < n; ++i) System.out.print(ans.get(i) + " "); } // Driver Code public static void main(String[] args) { // Given Input n = 4; ArrayList<Integer> mat = new ArrayList<>(); mat.add(2); mat.add(1); mat.add(2); mat.add(3); mat.add(4); mat.add(3); mat.add(2); mat.add(6); mat.add(1); mat.add(1); mat.add(2); mat.add(2); mat.add(1); mat.add(2); mat.add(3); mat.add(2); // Function Call restoreArray(mat); }}// This code is contributed by phasing17. |
Python3
# Python 3 program for the above approachfrom typing import Listdef gcd(a: int, b: int) -> int: """Function to calculate GCD of two numbers""" return a if b == 0 else gcd(b, a % b)def restore_array(mat: List[int]) -> List[int]: """Function to generate an N-length array having GCD of all pairs present in the array mat[][]""" cnt = {} # Stores the required array ans = [0] * n for i in range(n * n): # Store frequencies in dictionary # in decreasing order cnt[-mat[i]] = cnt.get(-mat[i], 0) + 1 pos = n - 1 for k in sorted(cnt, key=lambda x: -x): x = -k while cnt[k] > 0: # gcd(x, x) ans[pos] = x cnt[k] -= 1 # Remove all GCDs for # indices pos + 1 -> n - 1 for i in range(pos + 1, n): cnt[-gcd(ans[pos], ans[i])] = cnt.get(-gcd(ans[pos], ans[i]), 0) - 2 # Decreasing pos pos -= 1 # Return restored array return reversed(ans)# Given Inputn = 4mat = [2, 1, 2, 3, 4, 3, 2, 6, 1, 1, 2, 2, 1, 2, 3, 2]# Function Callans = restore_array(mat)# Print restored arrayprint(*ans)# This code is contributed by phasing17. |
C#
using System;using System.Collections.Generic;class Program { static int GCD(int a, int b) { // Function to calculate GCD of two numbers return b == 0 ? a : GCD(b, a % b); } static List<int> RestoreArray(List<int> mat, int n) { // Function to generate an N-length array having GCD // of all pairs present in the array mat[][] var cnt = new Dictionary<int, int>(); // Stores the required array var ans = new int[n]; for (int i = 0; i < n * n; i++) { // Store frequencies in dictionary // in decreasing order int value = -mat[i]; if (!cnt.ContainsKey(value)) { cnt[value] = 1; } else { cnt[value]++; } } int pos = n - 1; List<int> keys = new List<int>(cnt.Keys); keys.Sort(); foreach(int k in keys) { int x = -k; while (cnt[k] > 0) { // gcd(x, x) pos = pos % ans.Length; ans[pos] = x; cnt[k]--; // Remove all GCDs for // indices pos + 1 -> n - 1 for (int i = pos + 1; i < n; i++) { int g = GCD(ans[pos], ans[i]); if (cnt.ContainsKey(-g)) { cnt[-g] -= 2; } else { cnt[-g] = -2; } } // Decreasing pos pos--; } } // Return restored array return new List<int>(ans); } static void Main(string[] args) { // Given Input int n = 4; List<int> mat = new List<int>{ 2, 1, 2, 3, 4, 3, 2, 6, 1, 1, 2, 2, 1, 2, 3, 2 }; // Function Call List<int> ans = RestoreArray(mat, n); // Print restored array Console.WriteLine(string.Join(" ", ans)); }} |
Javascript
// JavaScript equivalent of the above codefunction gcd(a, b) { // Function to calculate GCD of two numbers return b == 0 ? a : gcd(b, a % b);}function restoreArray(mat) { // Function to generate an N-length array having GCD of all pairs present in the array mat[][] let cnt = {}; // Stores the required array let ans = Array(n).fill(0); for (let i = 0; i < n * n; i++) { // Store frequencies in dictionary // in decreasing order if (!cnt.hasOwnProperty(-mat[i])) cnt[-mat[i]] = 1; else cnt[-mat[i]] += 1; } let pos = n - 1; let keys = (Object.keys(cnt)).map(Number); keys.sort((a, b) => a - b) for (let k of keys) { let x = -(k); while (cnt[k] > 0) { // gcd(x, x) pos %= ans.length ans[pos] = x; cnt[k] -= 1 // Remove all GCDs for // indices pos + 1 -> n - 1 for (let i = pos + 1; i < n; i++) { let g = gcd(ans[pos], ans[i]); if (cnt.hasOwnProperty(-g)) cnt[-g] -= 2; else cnt[-g] = -2 } // Decreasing pos pos--; } } // Return restored array return ans}// Given Inputlet n = 4;let mat = [2, 1, 2, 3, 4, 3, 2, 6, 1, 1, 2, 2, 1, 2, 3, 2];// Function Calllet ans = restoreArray(mat);// Print restored arrayconsole.log(...ans);// This code is contributed by phasing17. |
Output:
2 3 4 6
Time Complexity: O(N2LogN)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
