Given a sequence of distinct numbers a1,a2,a3……..an, an inversion occurs if there are indices iaj For example in the sequence 2 1 4 3 there are 2 inversions (2 1) and (4 3) The input will be main sequence of N positive integers. From this sequence, a derived sequence Will be obtained using the following rule. The output is the number of inversions in the derived sequence Rules for forming derived sequence The derived sequence is formed by counting the number of 1’s 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 11100 and 1000. The derived sequence is the number of 1’s in the binary representation of the number in the input sequence and is 2,1,1.
Constraints:
N<=50
Integers in sequence<=10^7
Input Format:
First line of input will have a single integer, which will give N.
The next line will consists of comma separated string of N integers, which is the main sequence.
Output:
The number of inversions in the derived sequence formed from the main sequence.
Example 1
Input:
5
55 53 88 27 33
Output:
8
Explanation:
The number of integers is 5, as specified in the first line. The given sequence is 55, 53, 88, 27, 33. The binary representation is 110111,110101, 1011000, 11011, 100001and 100001. The derived sequence is 5,4,3,4,2, 4,3,4,2 (corresponding to the number of 1s bits). The number of inversions in this is 8, namely (5,4),(5,3),(5,4),(5,2),(4,3),(4,2),(3,2),(4,2). Hence the output is 8.
Example 2
Input:
8
120 21 47 64 72 35 18 98
Output:
15
Solution: In Python 3
def decimalToBinary(n):
return bin(n).replace("0b", "")
N=int(input())
Numbers=[]
A=[]
c=0
if(N<=50):
Numbers=list(map(int,input().split()))
for _i_ in Numbers:
BinaryNo=decimalToBinary(_i_)
n=BinaryNo.count('1')
A.append(n)
for i in range(N):
for j in range(i+1,N):
if(A[i]>A[j]):
c=c+1
print(c)Also Checkout