Skip to main content

Count Bits Problem

Count Bits


Problem Description

Given a sequence of distinct numbers a1, a2, ….. an, an inversion occurs if there are indices i<j such that ai > aj .

For example, in the sequence 2 1 4 3 there are 2 inversions (2 1) and (4 3).

The input will be a main sequence of N positive integers. From this sequence, a Derived derived sequence will be obtained using the following rule. The output is the number of inversions in the derived sequence.

Rule for forming derived sequence

The derived sequence is formed by counting the number of 1s bits in the binary representation of the corresponding number in the input sequence.

Thus, if the input is 3,4,8, the binary representation of the numbers are 11,100 and 1000. The derived sequence is the number of 1sin the binary representation of the numbers in the input sequence, and is 2,1,1


 Solution

def getInvCount(arr, n):
    inv_count = 0
    for i in range(n):
        for j in range(i+1, n):
            if (arr[i] > arr[j]):
                inv_count += 1
    return inv_count
# Driver Code
arr = [1, 20, 6, 4, 5]
n = len(arr)
print("Number of inversions are",
              getInvCount(arr, n))

Comments

Post a Comment

Popular posts from this blog

JAVA program of showing the student marksheet

package june13; import java.util.Scanner; public class student { int roll; String name; String email; int hindi,english,physics,chemistry,maths; void  input_details(){ System.out.println("please enter the following details "); Scanner sc= new Scanner(System.in); System.out.println("enter the roll number "); roll=sc.nextInt(); System.out.println("enter the name of student "); name=sc.next(); System.out.println(" enter the email"); email=sc.next(); System.out.println(" enter the marks of hindi "); hindi=sc.nextInt(); System.out.println("enter the marks of english "); english=sc.nextInt(); System.out.println(" enter the marks of physics ");; physics=sc.nextInt(); System.out.println(" enter the marks of chemistry "); chemistry=sc.nextInt(); System.out.println("enter the marks of maths "); maths=sc.nextInt(); ...
1 comment
Read more

Program of Making a simple calculator using java swing

import javax.swing.*; import java.awt.event.*; class Calc implements ActionListener {     JFrame f;     JTextField t;     JButton b1,b2,b3,b4,b5,b6,b7,b8,b9,b0,bdiv,bmul,bsub,badd,bdec,beq,bdel,bclr;     static double a=0,b=0,result=0;     static int operator=0;     Calc()     {         f=new JFrame("Calculator");         t=new JTextField();         b1=new JButton("1");         b2=new JButton("2");         b3=new JButton("3");         b4=new JButton("4");         b5=new JButton("5");         b6=new JButton("6");         b7=new JButton("7");         b8=new JButton("8");         b9=new JButton("9");         b0=new JButton("0");         b...
Post a Comment
Read more

C Program to find next larger number from a given array from target number

  Here is Program:   #include<stdio.h> #include<stdlib.h>   void sort(int arr[] ,int n)  {   int i,j,temp;   for (i = 0 ; i < ( n - 1 ); i++)   {     for (j = i+1 ; j <( n - 1); j++)     {       if (arr[i] > arr[j])       {         temp  = arr[i];         arr[i]   = arr[j];         arr[j] = temp;       }      }    }   }   int main()   {     int a[] = {2,11,11,6,80};     int i, num1 = 8;     sort(a,5);         for(i=0;i<sizeof(a)/sizeof(a[i]);i++)     {         if(a[4]<num1)          {   ...
Post a Comment
Read more