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
Find the minimum length of expression that can be expressed as the exponential of binary number

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 num1(plus). Here is my codepublic 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(n1)); else return getMin(n>>1); }


@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.

@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(n1)

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(n1)==dp.end()) dp[n1]=getmin(n1); return 1+min(dp[n+1],dp[n1]); } else { if(dp.find(n>>1)==dp.end()) dp[n>>1]=getmin(n>>1); return dp[n>>1]; } }

There might be a followup 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(n1, 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; }