Count of pairs of Array elements which are divisible by K when concatenated | Java program to count pairs of array elements which are divisible by K when concatenated ; Function to calculate and return the count of pairs ; Compute power of 10 modulo k ; Calculate length of a [ i ] ; Increase count of remainder ; Calculate ( a [ i ] * 10 ^ lenj ) % k ; Calculate ( k - ( a [ i ] * 10 ^ lenj ) % k ) % k ; Increase answer by count ; If a pair ( a [ i ] , a [ i ] ) is counted ; Return the count of pairs ; Driver code
import java . util . * ; import java . lang . * ; class GFG { static int [ ] [ ] rem = new int [ 11 ] [ 11 ] ; static int countPairs ( int [ ] a , int n , int k ) { int [ ] len = new int [ n ] ; int [ ] p = new int [ 11 ] ; p [ 0 ] = 1 ; for ( int i = 1 ; i <= 10 ; i ++ ) { p [ i ] = ( p [ i - 1 ] * 10 ) % k ; } for ( int i = 0 ; i < n ; i ++ ) { int x = a [ i ] ; while ( x > 0 ) { len [ i ] ++ ; x /= 10 ; } rem [ len [ i ] ] [ a [ i ] % k ] ++ ; } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 1 ; j <= 10 ; j ++ ) { int r = ( a [ i ] * p [ j ] ) % k ; int xr = ( k - r ) % k ; ans += rem [ j ] [ xr ] ; if ( len [ i ] == j && ( r + a [ i ] % k ) % k == 0 ) ans -- ; } } return ans ; } public static void main ( String [ ] args ) { int [ ] a = { 4 , 5 , 2 } ; int n = a . length , k = 2 ; System . out . println ( countPairs ( a , n , k ) ) ; } }