# Find the minimum length of expression that can be expressed as the exponential of binary number

• e.g: input = 28
28 = 2^4 + 2^3 + 2^2 => num = 3
28 = 2^5 - 2^2 => num = 2
So output should be 2

• Here is my thought
Scan the binary representation of the number from the right to left and find the position of least significant 1. recursively call num+1(minus) or num-1(plus). Here is my code

``````public static int getMin(int n){
if(n<=0) return 0;
if(n==1) return 1;
if((n & 1)==1) return 1 + Math.min(getMin(n+1),getMin(n-1));
else return getMin(n>>1);
}``````

• Hi ZackerZ, could you share more for your algorithm? Try it with number 56789.
Function getMin(56789) returns 7, but the answer is 6

56789 = 2^16 - 2^1 - 2^3 - 2^5 - 2^9 - 2^13

• @elmirap Hi elmirap, I found that 2^16 - 2^1 - 2^3 - 2^5 - 2^9 - 2^13 = 56790.

• sorry, my mistake

• @elmirap you can think of it like a greedy algorithm. You start searching from the lease significant bit.. Because you only have two operation: either add or minus, so the result must come from one of them. As for the running time, if there is only 32 bit, the running time should be 0(1)

• @ZhackerZ Thank you very much!
Addition of 1 is clear for me . For example if we have some number 0001111 and you add one you will decrease number of powers with 4 , because 0001111 + 1 = 0010000, but it is not still clear for me why substraction of 1 works, how solution is improved with substraction.

• This solution looks elegant!

• @ZhackerZ Thanks for the brilliant solution!
There is a lot of recurrence though, we can use a hash map to store getMin(n+1) and getMin(n-1)

• ``````unordered_map<int, int> dp;

int getmin(int n)
{
cout<<n<<endl;
if(n<=0) return 0;
if(n==1) return 1;
if(n&1){
if(dp.find(n+1)==dp.end()) dp[n+1]=getmin(n+1);
if(dp.find(n-1)==dp.end()) dp[n-1]=getmin(n-1);
return 1+min(dp[n+1],dp[n-1]);
}
else
{
if(dp.find(n>>1)==dp.end()) dp[n>>1]=getmin(n>>1);
return dp[n>>1];
}
}``````

• There might be a follow-up question. "Can you print out the expression with the minimum length? Then, we need to do the backtracking.
The following are my implementation:

public Map<Integer,Integer> map = new HashMap<Integer,Integer>();
public Map<Integer,String> paths = new HashMap<Integer,String>();

``````public int findMinBinary(int n){
//map = new HashMap<Integer,Integer>();
//paths = new HashMap<Integer,String>();
paths.put(0, "");
paths.put(1, "2^0");
paths.put(2, "2^1");
StringBuilder path = new StringBuilder();
int ret = findMinBinary(n,0, path);
System.out.println(path);
return ret;
}
private int findMinBinary(int n, int digit, StringBuilder path){
if (n<=0) {
path.append("2^").append(digit);
return 0;
}
if (n==1) {
path.append("2^").append(digit);
return 1;
}
if ( map.containsKey(n) ) {
path.append(paths.get(n));
return map.get(n);
}
int ret = 0;
if ( (n & 1) == 1) {
StringBuilder up_str = new StringBuilder();
StringBuilder down_str = new StringBuilder();
int up = findMinBinary(n+1, digit, up_str );
int down = findMinBinary(n-1, digit, down_str );
ret = 1;
if ( up < down ) {
ret += up;
path.append(up_str).append(" - 2^").append(digit);
} else {
ret += down;
path.append(down_str).append(" + 2^").append(digit);
}
} else {
ret = findMinBinary(n>>1, digit+1, path);
}
paths.put(n, path.toString() );
map.put(n, ret);
return ret;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.