top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Writer's pictureilluminati

Different Bits Sum Pairwise - InterviewBit Solution


Problem Description:

We define f(X, Y) as a number of different corresponding bits in the binary representation of X and Y. For example, f(2, 7) = 2, since binary representation of 2 and 7 are 010 and 111, respectively. The first and the third bit differ, so f(2, 7) = 2.

You are given an array of N positive integers, A1, A2,…, AN. Find the sum of f(Ai, Aj) for all pairs (i, j) such that 1 ≤ i, j ≤ N. Return the answer modulo 109+7.


For example,

A=[1, 3, 5]

We return

f(1, 1) + f(1, 3) + f(1, 5) + 
f(3, 1) + f(3, 3) + f(3, 5) +
f(5, 1) + f(5, 3) + f(5, 5) =

0 + 1 + 1 +
1 + 0 + 2 +
1 + 2 + 0 = 8

Solution Approach:



Solution in C++:

If you have any questions or queries, feel free to drop a comment in the comments section below.

Note: Help us improve this blog

If you have a better solution, and you think you can help your peers to understand this problem better, then please drop your solution and approach in the comments section below.

We will upload your approach and solution here by giving you the proper credit so that you can showcase it among your peers.

1 Comment


Kamal Aroro
Kamal Aroro
Jun 28, 2022

int Solution::cntBits(vector<int> &A) { int ans=0; for(int i =0;i<A.size();i++) { for(int j=0;j<A.size();j++) { ans+=__builtin_popcount(A[i]^A[j]); ans=ans%1000000007; } } return ans; } why this is showing TLE in hight cases

Like
bottom of page