Count pairs made up of an element divisible by the other from an array consisting of powers of 2 | C # program for the above approach ; Function to count the number of pairs as per the given conditions ; Initialize array set_bits as 0 ; Store the total number of required pairs ; Traverse the array arr [ ] ; Store arr [ i ] in x ; Store the position of the leftmost set bit in arr [ i ] ; Increase bit position ; Divide by 2 to shift bits in right at each step ; Count of pairs for index i till its set bit position ; Increasing count of set bit position of current elelement ; Print the answer ; Driver Code ; Function Call
using System ; class GFG { static void numberOfPairs ( int [ ] arr , int N ) { int [ ] set_bits = new int [ 31 ] ; for ( int i = 0 ; i < N ; i ++ ) { set_bits [ i ] = 0 ; } int count = 0 ; for ( int i = 0 ; i < N ; i ++ ) { int x = arr [ i ] ; int bitpos = - 1 ; while ( x > 0 ) { bitpos ++ ; x /= 2 ; } for ( int j = 0 ; j <= bitpos ; j ++ ) { count += set_bits [ j ] ; } set_bits [ bitpos ] ++ ; } Console . Write ( count ) ; } static public void Main ( ) { int [ ] arr = { 4 , 16 , 8 , 64 } ; int N = arr . Length ; numberOfPairs ( arr , N ) ; } }