Count Pairs with Same Most Significant Bit
Given N integers, count the number of pairs (i, j) such that 1 <= i < j <= N and the most significant bit (MSB) of the i-th number is the same as the most significant bit of the j-th number. The most significant bit of a positive integer is the leftmost '1' in its binary representation. For example, the MSB of 13 (binary 1101) is the bit corresponding to 8 (2^3). The MSB of 6 (binary 110) is the bit corresponding to 4 (2^2). If two numbers have the same MSB position, they are considered to have the same MSB.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer: the count of pairs (i, j) with i < j where the i-th and j-th numbers have the same most significant bit.
Constraints
1 <= N <= 1000 1 <= a[i] <= 10^9
Example 1
5 1 2 3 4 5
2
Pairs with same MSB: (1,2), (1,3), (1,4), (1,5) -> MSB=1; (2,3) -> MSB=2; (4,5) -> MSB=4. Total 4+1+1 = 6.
Example 2
3 10 20 30
1
10 (1010), 20 (10100), 30 (11110). MSBs are 8, 16, 16. Pair (20, 30) has same MSB (16). Count is 1.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 5
3 10 20 30