Given an array arr[] which consists of all the divisors of two integers A and B (along with A, B, and 1). The task is to find A and B from the given array.
Note: If a number is a divisor of both A and B then it will be present twice in the array.
Examples:
Input: arr[] = {1, 2, 4, 8, 16, 1, 2, 3, 6}
Output: A = 16, B = 6
1, 2, 4, 8 and 16 are the divisors of 16
1, 2, 3 and 6 are the divisors of 6Input: arr[] = {1, 2, 4, 8, 16, 1, 2, 4}
Output: A = 16, B = 4
Approach: From the given array, as all the elements are divisors of either A or B then it is compulsory that the largest element of the array will be either A or B. For simplicity take it as A. Now, there are two cases which is applicable for an element to be B:
- B can be the largest element which is not a divisor of A.
- B can be the largest element smaller than A whose frequency is 2.
In order to find the value of A and B, sort the array. Print largest element as A and then the largest element which is either not a divisor of A or having frequency 2 will be B.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print A and B all of whose// divisors are present in the given arrayvoid printNumbers(int arr[], int n){ // Sort the array sort(arr, arr + n); // A is the largest element from the array int A = arr[n - 1], B = -1; // Iterate from the second largest element for (int i = n - 2; i >= 0; i--) { // If current element is not a divisor // of A then it must be B if (A % arr[i] != 0) { B = arr[i]; break; } // If current element occurs more than once if (i - 1 >= 0 && arr[i] == arr[i - 1]) { B = arr[i]; break; } } // Print A and B cout << "A = " << A << ", B = " << B;}// Driver codeint main(){ int arr[] = { 1, 2, 4, 8, 16, 1, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); printNumbers(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GfG { // Function to print A and B all of whose // divisors are present in the given array static void printNumbers(int arr[], int n) { // Sort the array Arrays.sort(arr); // A is the largest element from the array int A = arr[n - 1], B = -1; // Iterate from the second largest element for (int i = n - 2; i >= 0; i--) { // If current element is not a divisor // of A then it must be B if (A % arr[i] != 0) { B = arr[i]; break; } // If current element occurs more than once if (i - 1 >= 0 && arr[i] == arr[i - 1]) { B = arr[i]; break; } } // Print A and B System.out.print("A = " + A + ", B = " + B); } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 4, 8, 16, 1, 2, 4 }; int n = arr.length; printNumbers(arr, n); }} |
Python3
# Python3 implementation of the approach # Function to print A and B all of whose # divisors are present in the given array def printNumbers(arr, n): # Sort the array arr.sort() # A is the largest element from the array A, B = arr[n - 1], -1 # Iterate from the second largest element for i in range(n - 2, -1, -1): # If current element is not a divisor # of A then it must be B if A % arr[i] != 0: B = arr[i] break # If current element occurs more than once if i - 1 >= 0 and arr[i] == arr[i - 1]: B = arr[i] break # Print A and B print("A =", A, ", B =", B) # Driver code if __name__ == "__main__": arr = [1, 2, 4, 8, 16, 1, 2, 4] n = len(arr) printNumbers(arr, n)# This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System.Collections;using System;class GfG { // Function to print A and B all of whose // divisors are present in the given array static void printNumbers(int []arr, int n) { // Sort the array Array.Sort(arr); // A is the largest element from the array int A = arr[n - 1], B = -1; // Iterate from the second largest element for (int i = n - 2; i >= 0; i--) { // If current element is not a divisor // of A then it must be B if (A % arr[i] != 0) { B = arr[i]; break; } // If current element occurs more than once if (i - 1 >= 0 && arr[i] == arr[i - 1]) { B = arr[i]; break; } } // Print A and B Console.WriteLine("A = " + A + ", B = " + B); } // Driver code public static void Main() { int []arr = { 1, 2, 4, 8, 16, 1, 2, 4 }; int n = arr.Length; printNumbers(arr, n); }}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach// Function to print A and B all of whose// divisors are present in the given arrayfunction printNumbers($arr, $n){ // Sort the array sort($arr); // A is the largest element from the array $A = $arr[$n - 1]; $B = -1; // Iterate from the second largest element for ($i = $n - 2; $i >= 0; $i--) { // If current element is not a divisor // of A then it must be B if ($A % $arr[$i] != 0) { $B = $arr[$i]; break; } // If current element occurs more than once if ($i - 1 >= 0 && $arr[$i] == $arr[$i - 1]) { $B = $arr[$i]; break; } } // Print A and B echo("A = " . $A . ", B = " . $B);}// Driver code$arr = array( 1, 2, 4, 8, 16, 1, 2, 4 );$n = sizeof($arr);printNumbers($arr, $n);// This code is contributed by Code_Mech. |
Javascript
<script>// Javascript implementation of the approach// Function to print A and B all of whose// divisors are present in the given arrayfunction printNumbers(arr, n){ // Sort the array arr.sort((a,b)=>{return a-b;}); // A is the largest element from the array var A = arr[n - 1], B = -1; // Iterate from the second largest element for (var i = n - 2; i >= 0; i--) { // If current element is not a divisor // of A then it must be B if ((A % arr[i]) != 0) { B = arr[i]; break; } // If current element occurs more than once if (i - 1 >= 0 && arr[i] == arr[i - 1]) { B = arr[i]; break; } } // Print A and B document.write( "A = " + A + ", B = " + B);}// Driver codevar arr = [ 1, 2, 4, 8, 16, 1, 2, 4 ];var n = arr.length;printNumbers(arr, n);</script> |
Output:
A = 16, B = 4
Time Complexity: O(nlog(n))
Auxiliary Space: O(1)
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!
