Minimum number of powers of 2 to get an Integer?

Question

I was asked below question in an interview:

Every number can be described via the addition and subtraction of powers of 2. For example, 29 = 2^0 + 2^2 + 2^3 + 2^4. Given an int n, return minimum number of additions and subtractions of 2^i to get n.

Example 1:

Input: 15
Output: 2
Explanation: 2^4 - 2^0 = 16 - 1 = 15

Example 2:

Input: 8
Output: 1

Example 3:

Input: 0
Output: 0

Below is what I got but is there any way to improve this or is there any better way to solve above problem?

  public static int minPowerTwo(int n) {
    if (n == 0) {
      return 0;
    }
    if (Integer.bitCount(n) == 1) {
      return 1;
    }
    String binary = Integer.toBinaryString(n);
    StringBuilder sb = new StringBuilder();
    sb.append(binary.charAt(0));
    for (int i = 0; i < binary.length() - 1; i++) {
      sb.append('0');
    }
    int min = Integer.parseInt(sb.toString(), 2);

    sb.append('0');
    int max = Integer.parseInt(sb.toString(), 2);

    return 1 + Math.min(minPowerTwo(n - min), minPowerTwo(max - n));
  }

Answer 1

Well... we can deduce that each power of two should be used only once, because otherwise you can get the same result a shorter way, since 2^x + 2^x = 2^x+1, -2^x - 2^x = -2^x+1, and 2^x - 2^x = 0.

Considering the powers used in order, each one has to change the corresponding bit from an incorrect value to the correct value, because there will be no further opportunities to fix that bit, since each power is used only once.

When you need to add or subtract, the difference is what happens to the higher bits:

000000    000000    111100    111100
 + 100     - 100     + 100    -  100
------    ------    ------    ------
000100    111100    000000    111000

One way, all the higher bits are flipped. The other way they are not.

Since each decision can independently determine the state of all the higher bits, the consequences of choosing between + or - are only relevant in determining the next power of 2.

When you have to choose + or -, one choice will correct 1 bit, but the other choice will correct 2 bits or more, meaning that the next bit that requires correction will be higher.

So, this problem has a very straightforward solution with no dynamic programming or searching or anything like that:

1. Find the smallest power of 2 that needs correction.
2. Either add it or subtract it. Pick the option that corrects 2 bits.
3. Repeat until all the bits are correct

in java, that would look like this. Instead of finding the operations required to make the value, I'll find the operations required to change the value to zero, which is the same thing with opposite signs:

int minPowersToFix(int val) {
    int result = 0;
    while(val!=0) {
        ++result;
        int firstbit = val&-val; //smallest bit that needs fixed
        int pluscase = val+firstbit;
        if ((pluscase & (firstbit<<1)) == 0) {
            val+=firstbit;
        } else {
            val-=firstbit;
        }
    }
    return result;
}

Answer 2

And, here is a test case to check whether a solution is correct, written in Java.

(It was written for my solution, which is proven not correct in some case, so I removed that answer, but the test case is still relevant.)

Matt Timmermans's answer passes all the test cases, including negative numbers.

And, Integer.bitCount(val ^ (3 * val)) passes most of them, except when input is Integer.MAX_VALUE.

---

Code

MinCountOf2PowerTest.java

import org.testng.Assert;
import org.testng.annotations.Test;

public class MinCountOf2PowerTest {
    @Test
    public void testPositive() {
        // no flip,
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01010001", 2)), 3);

        // flip,
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0111", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01111", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.MAX_VALUE), 2);

        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01101", 2)), 3);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011011", 2)), 3);

        // flip, there are multiple flippable location,
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0100000111", 2)), 3);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("010010000000111", 2)), 4);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0100100000001111111", 2)), 4);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("010011000000001111111", 2)), 5);
    }

    @Test
    public void testZero() {
        Assert.assertEquals(MinCountOf2Power.minCount(0), 0);
    }

    @Test
    public void testNegative() {
        Assert.assertEquals(MinCountOf2Power.minCount(-1), 1);
        Assert.assertEquals(MinCountOf2Power.minCount(-9), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(-100), 3);
    }

    // a positive number has the same result as its negative number,
    @Test
    public void testPositiveVsNegative() {
        for (int i = 1; i <= 1000; i++) {
            Assert.assertEquals(MinCountOf2Power.minCount(i), MinCountOf2Power.minCount(-i));
        }
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.MAX_VALUE), MinCountOf2Power.minCount(-Integer.MAX_VALUE));
    }

    // corner case - ending 0,
    @Test
    public void testCornerEnding0() {
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01110", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011110", 2)), 2);

        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011100", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0111000", 2)), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01110000", 2)), 2);
    }

    // input from OP's question, refer: https://stackoverflow.com/questions/57797157
    @Test
    public void testOpInput() {
        Assert.assertEquals(MinCountOf2Power.minCount(15), 2);
        Assert.assertEquals(MinCountOf2Power.minCount(8), 1);
        Assert.assertEquals(MinCountOf2Power.minCount(0), 0);
    }
}

Tips:

• It's written in Java, and use TestNG.
  • But you can use JUnit instead simply by replacing the import statement, I guess.
  • Or translate to other languages by coping the input / output value pairs with specific syntax.
• I also found that a positive integer always has the same result as its negative number.
  And there is a test case included to proved that.