Number of array elements derivable from D after performing certain operations | Java program to find the number of array elements which can be derived by perming ( + A , - A , + B , - B ) operations on D ; Function to return gcd of a and b ; Function to Return the number of elements of arr [ ] which can be derived from D by performing ( + A , - A , + B , - B ) ; find the gcd of A and B ; counter stores the number of array elements which can be derived from D ; arr [ i ] can be derived from D only if | arr [ i ] - D | is divisible by gcd of A and B ; Driver Code
import java . io . * ; class GFG { static int gcd ( int a , int b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } static int findPossibleDerivables ( int arr [ ] , int n , int D , int A , int B ) { int gcdAB = gcd ( A , B ) ; int counter = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ( Math . abs ( arr [ i ] - D ) % gcdAB ) == 0 ) { counter ++ ; } } return counter ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 4 , 7 , 13 } ; int n = arr . length ; int D = 5 , A = 4 , B = 2 ; System . out . println ( findPossibleDerivables ( arr , n , D , A , B ) ) ; int a [ ] = { 1 , 2 , 3 } ; n = a . length ; D = 6 ; A = 3 ; B = 2 ; System . out . println ( findPossibleDerivables ( a , n , D , A , B ) ) ; } }