I need more efficient way to solve this, how to i remove complexity?
Playing with bits
Efficient solution is based on the fact that if we store count of all set bits of numbers in an array “BitCounts”, then we answer each query in O(1) time. So, start traversing the elements of array and count set bits for each element and store in array. Now, find cumulative sum of this array. This array will help in answering queries.
BitCount[] that will store the count of set bits
in a number.
Run a Loop from 0 to 31 "for 32 bits size integer "
-> mark elements with i’th bit set
Run an inner Loop from 0 to size of Array “Arr”
-> Check whether the current bit is set or not
-> if it’s set then mark it.
long temp = arr[j] >> i;
if (temp %2 != 0)
BitCount[j] += 1
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.