GCD of Different SubSequences in Java
The positive numbers are provided in an array called inArr. The aim is to determine the number of distinct GCDs (Greatest Common Divisors) in each subsequence present in the input array. A note subsequence is created by selecting one or more elements at a time from an array.
Brute Force Approach
According to this method, we will compute each subsequence of the input array and store them in an array list. After that compute the GCD for each subsequence contained in the array list, we will group them into sets. The size of the set will be our response because the set only consists of distinct components. Recursion will be used to find the subsequences. Take note of the programme below.
GCDDiff1.java
// importing important required packages
import java . util . ArrayList ;
import java . util . Set ;
import java . util . HashSet ;
// public class with name GCDDiff1 is created
public class GCDDiff1
{
// arraylist with name arrlist is created
ArrayList <ArrayList<Integer>> arrlist = new ArrayList <ArrayList<Integer>> ( ) ;
Set<Integer> set = new HashSet<Integer> ( ) ;
// public method to finf sub sequence
public void find_sub_seq ( int arr1 [ ] , int size , int i1 , ArrayList < Integer > tempvalue )
{
if ( i1 >= size )
{
ArrayList < Integer > t1 = new ArrayList < Integer > ( ) ;
for ( int idx1 = 0 ; idx1 < tempvalue . size ( ) ; idx1++ )
{
t1 . add ( tempvalue . get ( idx1 ) ) ;
}
arrlist .add( t1 ) ;
return ;
}
tempvalue . add ( arr1 [ i1 ] ) ;
find_sub_seq ( arr1 , size , i1 + 1 , tempvalue ) ;
int index1 = tempvalue . size() – 1 ;
tempvalue . remove ( index1 ) ;
find_sub_seq ( arr1 , size , i1 + 1 , tempvalue ) ;
}
// public method to find gcd
public int find_GCD ( int num1 , int num2 )
{
if ( num1 == 0 )
{
return num2 ;
}
return find_GCD ( num2 % num1 , num1 ) ;
}
// public method to find gcd of the subsequences
public void find_GCD_sub_seq ( ArrayList < Integer > arrlist1 )
{
// if array size is 0 return
if ( arrlist1 . size ( ) == 0 )
{
return ;
}
// if array size is 1 return
if ( arrlist1 . size ( ) == 1 )
{
set . add ( arrlist1 . get ( 0 ) ) ;
return ;
}
// assigning two integer variables to first two values of
int t11 = arrlist1 . get ( 0 ) ;
int t22 = arrlist1 . get( 1 ) ;
int tt = find_GCD ( t11 , t22 ) ;
for ( int i1 = 2; i1 < arrlist1 . size ( ) ; i1++ )
{
tt = find_GCD ( tt , arrlist1 . get ( i1 ) ) ;
}
Set . add ( tt ) ;
}
public void find_GCD_Util()
{
int size1 = arrlist . size();
for ( int i1 = 0 ; i1 < size1 ; i1++ )
{
find_GCD_sub_seq ( arrlist . get ( i1 ) ) ;
}
}
// main section where execution of the program starts
public static void main ( String args [ ] )
{
GCDDiff1 object1 = new GCDDiff1 ( ) ;
int inarr [ ] = {4 , 6 , 8 } ;
int size = inarr . length ;
ArrayList < Integer > tempvalue = new ArrayList < Integer > ( ) ;
object1 . find_sub_seq ( inarr , size , 0 , tempvalue ) ;
object1 . find_GCD_Util ( ) ;
System . out . println ( " For the input array: " ) ;
for ( int i1 = 0 ; i1 < size ; i1++ )
{
System . out . print ( inarr [ i1 ] + " " ) ;
}
System . out . println ( ) ;
System . out . println ( " The total number of unique GCDs is: " + object1 . set . size ( ) ) ;
System . out . println ( ) ;
object1 . set = new HashSet < Integer > ( ) ;
object1 . arrlist = new ArrayList < ArrayList < Integer > > ( ) ;
int inarr1 [ ] = {3 , 6 , 9 } ;
size = inarr1 . length ;
tempvalue = new ArrayList < Integer > ( ) ;
object1 . find_sub_seq ( inarr1 , size , 0 , tempvalue ) ;
object1 . find_GCD_Util ( ) ;
System . out . println ( " For the input array: " ) ;
for( int i1 = 0; i1 < size; i1++ )
{
System . out . print ( inarr1 [ i1 ] + " " ) ;
}
System . out . println ( ) ;
System . out . println ( " The total number of unique GCDs is: " + object1 . set . size ( ) ) ;
}
}
Output
Effective Approach:
We are able to perform the optimization using the greedy method. The GCD of any two numbers, n1 and n2, must lie between 1 and a maximum of ( n1 , n2 ) , and the same principle holds true for any sequence with more than two members. The GCD will always fall between [ 1 , M ] if the highest element in a subsequence is M. As a result, if we iterate between 1 and M, and any integer in the range is a factor of one of the array's elements, we can display that element as one of the GCD's results.
GCDDiff2.java
import java . util . ArrayList ;
import java . util . Set ;
import java . util . HashSet ;
// public class
public class GCDDiff2
{
public int find_GCD ( int num1 , int num2 )
{
// if num1 is 0 return num2
if ( num1 == 0 )
{
return num2 ;
}
return find_GCD ( num2 % num1, num1 ) ;
}
public int find_GCDs_Sub_seq ( ArrayList < Integer > arrList )
{
ArrayList < Integer > ans = new ArrayList < Integer > ( ) ;
HashSet < Integer > hs1 = new HashSet < Integer > ( ) ;
for ( int i1 = 0 ; i1 < arrList . size ( ) ; i1++ )
{
hs1 . add ( arrList . get ( i1 ) ) ;
}
int Maximum = Integer . MIN_VALUE ;
for ( int i1 = 0; i1 < arrList . size ( ) ; i1++ )
{
if ( arrList . get ( i1 ) > Maximum )
{
Maximum = arrList . get ( i1 ) ;
}
}
for ( int j1 = 1 ; j1 <= Maximum ; j1++ )
{
int compute_GCD = 0 ;
for ( int k1 = j1 ; k1 < Maximum + 1 ; k1 += j1 )
{
if ( hs1 . contains ( k1 ) )
{
compute_GCD = find_GCD (compute_GCD , k1 ) ;
}
}
if ( compute_GCD == j1 )
{
ans . add ( j1 ) ;
}
}
return ans . size ( ) ;
}
// main section of the program where execution starts
public static void main ( String argvs [ ] )
{
// creating object to class
GCDDiff2 object1 = new GCDDiff2 ( ) ;
ArrayList < Integer > arrList1 = new ArrayList < Integer > ( ) ;
arrList1 . add ( 4 ) ;
arrList1 . add ( 6 ) ;
arrList1 . add ( 8 ) ;
int size = arrList1 . size ( ) ;
int ans = object1 . find_GCDs_Sub_seq ( arrList1 ) ;
System . out . println( " For the input array: " ) ;
for ( int i1 = 0 ; i1 < size ; i1++ )
{
System . out . print ( arrList1 . get ( i1 ) + " " ) ;
}
System . out . println ( ) ;
System . out . println ( " The total number of unique GCDs is: " + ans ) ;
System . out . println ( ) ;
ArrayList < Integer > arrList2 = new ArrayList < Integer > ( ) ;
arrList2 . add ( 3 ) ;
arrList2 . add ( 6 ) ;
arrList2 . add ( 9 ) ;
size = arrList2 . size ( ) ;
ans = object1 . find_GCDs_Sub_seq ( arrList2 ) ;
System . out . println ( " For the input array: " ) ;
for( int i1 = 0 ; i1 < size ; i1++ )
{
System . out . print ( arrList2 . get ( i1 ) + " " ) ;
}
System . out . println ( ) ;
System . out . println ( " The total number of unique GCDs is: " + ans ) ;
}
}
Output
