CODEWITHSUNDEEP
pythonalgorithmbit
Jason
Jason

Reputation: 39

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.

Upvotes: 1

Views: 1980

Answers (5)

Mr. Pyramid
Mr. Pyramid

Reputation: 3935

That's how I have solved this in Javascript

  function solution(A) {
    let binarian = 0;
    // only positive values
    A = A.filter((x) => x > -1);
    // get the total of the binarian
    for (let i = 0; i < A.length; i++) {
      binarian += Math.pow(2, A[i]);
    }
    // time to prepare your own binarian the shortest one!
    let b = [];
    while (binarian > 0) {
      let element = parseInt(Math.log2(binarian), 10);
      b.push(element);
      binarian -= Math.pow(2, element);
    }
    return b.length;
  }

Upvotes: 0

Zaman
Zaman

Reputation: 117

This is my solution in PHP

function solution($a){
    // write your code in PHP7.0
    $binarian = 0;
    foreach ($a as $val){
        $binarian += pow(2, $val);
    }

    $b = [];
    while($binarian > 0){
        $el = intval(log($binarian, 2));
        array_push($b, $el);
        $binarian -= pow(2, $el);
    }
    
    return $b;
    
}

Upvotes: 1

One Lyner
One Lyner

Reputation: 2004

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

Upvotes: 3

norlesh
norlesh

Reputation: 1831

Without outright answering what sounds like an assignment question, i'll just point out that any time you have a pair of 2x you can replace it with a single 2x+1... As for the actual algorithm since you don't need to care about the order of the members of A you should put them all into a bag/multiset structure and go from there as you build B.

Upvotes: 1

Green Cloak Guy
Green Cloak Guy

Reputation: 24691

# find the binarian
binarian = sum(2**a for a in A)
# find the powers of two that are present in A
# We do this by making a list of which bits are True in the binarian.
#   we check each bit, using len(bin()) to as an easy log2
#   we only include powers of two that produce 1 when and'ed with the binarian
B = [pwr for pwr in range(len(bin(binarian)) - 2) if (2**pwr & binarian)]

There's no way more efficient to construct a number out of powers of two, then to simply list which bits are flipped. This is what that does. It scans through bits from least-significant to most-significant, and only outputs if the bit is flipped.

This produces an ascending list (e.g. [0, 2, 3]. If you want a descending list (e.g. [3, 2, 0], you can wrap the range() call in reversed().

Upvotes: 0

Related Questions