Bit Manipulation, find another shortest array whose binarian is same as the given array’s binarian

Given an array A, its binarian(A) is defined as 2^A[0] + 2^A[1] + …. 2^A[n]; Questions asks to find anther shortest array B whose binarian(B) is same as A’s.

For example, A=[1,0,2,0,0,2]，thus if B=[3,2,0], this satisfies the requirements, and the output is 3.

Could you guys provide some ideas of how to solve this problem? Thanks.

Answer

Here’s a solution we add the power of 2 doing the carry propagation by hand. It can handle stupidly big inputs like A=[1000000000, 1000000000, 1000000001].

def shortest_equivalent_binarian(A): 
   s = set() 
   for a in A: 
       while a in s: # carry propagation
           s.remove(a) 
           a += 1 
       s.add(a) 
   return sorted(s, reverse=True)
# reverse is not necessary for correctness, but gives the same B as in your example