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


  • 0
    Z

    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


  • 0
    Z

    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);
        }

  • 0

    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


  • 0
    Z

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


  • 0

    sorry, my mistake


  • 0
    Z

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


  • 0

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


  • 0

    This solution looks elegant!


  • 0
    G

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


  • 0
    G
    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];
        }
    }

  • 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;
    }

Log in to reply
 

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