my java solution with memorization search, handling overflow test case


  • 6
    Z

    Same idea with other recursive solutions, but two ticky points here.

    1. With the helper of hashmap, we don't need to search for one intermediate result multiple times
    2. To hand the overflow for test case INT.MAX, use 1 + (n - 1) / 2 instead of (n + 1) / 2. The idea comes from solving some binary search questions. To avoid overflow, we use int mid = start + (end - start) / 2 instead of int mid = (start + end) / 2
    public class Solution {
        public int integerReplacement(int n) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            map.put(1, 0);
            map.put(2, 1);
    
            return helper(n, map);
        }
        
        private int helper(int n, Map<Integer, Integer> map) {
            if (map.containsKey(n)) {
                return map.get(n);
            }
            
            int steps = -1;
            if (n % 2 == 0) {
                steps = helper(n / 2, map) + 1;
            } else {
                steps = Math.min(helper((n - 1), map) + 1, helper(1 + (n - 1) / 2, map) + 2);
            }
            
            map.put(n, steps);
            
            return steps;
        }
    }
    

  • 0
    J
    This post is deleted!

  • 0
    J
    This post is deleted!

  • 0
    J
    public int integerReplacement(int n) {
    		if (1 == n)
    			return 0;
    		if (n + 1 <= 0) {
    			return 32;
    		}
    		int sum = 0;
    		while (n != 1) {
    			if (n % 2 == 0) {
    				n = n / 2;
    				sum++;
    			} else {
    				int np = n + 1;
    				int ns = n - 1;
    				sum++;
    				int delta_p = 0;
    				int delta_s = 0;
    
    				while (np % 2 == 0) {
    					delta_p++;
    					np = np / 2;
    				}
    
    				while (ns % 2 == 0) {
    					delta_s++;
    					ns = ns / 2;
    				}
    
    				if (np < ns) {
    					sum = sum + delta_p;
    					n = np;
    				} else {
    					sum = sum + delta_s;
    					n = ns;
    				}
    			}
    
    		}
    		return sum;
    	}
    

  • 0
    J

    @jackycoder 4ms with all the test cases passed .


Log in to reply
 

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