Sum of bit differences for all pairs in Java

Here you will learn to find the bit difference of all possible pairs of numbers and sum them up in Java Programming Language. This tutorial will give you a basic idea and some tricks to start your approach towards this problem.

Let’s first understand with an example of what we are up to in this specific problem and how to solve it with as less time complexity as possible,

Let us make up a process which we need to follow to obtain the output,

  • We will consider an array of integers.
  • Then we have to find all possible pairs of those array elements.
  • The next step, find the difference of there bit represented value.
  • Finally, we have to sum them up.

 

Input: array = {5,6}
Process: All possible pairs = {5,5}, {5,6}, {6,6}, {6,5}
         The difference in bit representation = 0, 2, 0, 2
         The Sum = 0 + 2 + 0 + 2 = 4
Output: 4

Note- Bit difference of 5 and 6 can be calculated as 5 is 101 and 6is 110 as bits, as the second and last bit differs in two numbers the difference is 2.

An easy solution here is, we can represent all the elements in the array in 32 bits and then traverse through the 0_th-bit index to 31st-bit index to count numbers having the i_th bit set.

  • We will assign the numbers which are i_th bit set.
  • We will also assign the numbers which are i_th bit not set with different variable names.
  • As both sets contribute exactly one to the final sum when they are multiplied.
  • 2 is multiplied considering the repetition factor.

Implementation:

import java.io.*;
public class SumDifference {
    public static void main(String args[])  
    { 
        int array[] = {5,6}; //array
        int n = array.length; 
        System.out.println(sumbit(array, n)); 
    } 
    static int sumbit(int array[], int n) //function
    {
        int result=0,i,j,set=0,not_set; //variables initialized
     
        for (i = 0; i < 32; i++) {  //traversing
           set = 0; 	//set numbers
                
           for (j = 0; j < n; j++) 
              if ((array[j] & (1 << i)) == 0) 
                 set++; 
    
           not_set=n-set;		// non set numbers
           result=result+(set * (not_set) * 2); //*2 for repetition
        } 
            
        return result; 
    } 
}

Output:

4

Leave a Reply