2 naive solutions + 2 smart solutions in Java, with detailed thinking process


  • 0

    So I hate to admit, I only came up with 2 somewhat similar naive solutions, which only works for number that is not too big.
    And solution 3 and 4 are accepted solutions which are smarter.
    Hope to share the thinking process from naive to smart solution.

    /*
    so looks like go down is not always the fastest route, such as 7.
    if n is even, the only option is to divided by 2 tho.
    we can use brutal force to dfs all the possible solitions, but looks like a dp might work here.
    we can build the path from 1 up to n.
    
    since we can go up to 2n. and we need 2 pass of the array.
    first pass calculate based on +1 and *2
    second pass calculate based on -1
    
    looks like we don't know how many passes there will be
    
    1.
    The first version of the solution was to use a while loop to sweep back and forth, until there is no changes.
    however we run into timelimit error
    
    
    public class Solution {
        public int integerReplacement(int n) {
            int[] record = new int[2*n + 1];
            for(int i = 0; i < record.length; i++){
                record[i] = Integer.MAX_VALUE;    
            } 
            record[1] = 0;
            boolean updated = true;
            boolean forward = true;
            while(updated){
                updated = false;
                if(forward){
                    for(int i = 2; i < 2*n +1; i++){
                        int temp = record[i];
                        if((i % 2) == 0){
                            record[i] = Math.min(record[i], Math.min(record[i/2], record[i - 1]) + 1); 
                        }else{
                            record[i] = Math.min(record[i], record[i-1] + 1);
                        }
                        if(temp != record[i] && i < n){
                            updated = true;
                        }
                    }
                    forward = false;
                }else{
                    for(int i = 2*n; i > 1; i--){
                        int temp = record[i-1];
                        record[i-1] = Math.min(record[i-1], record[i] + 1);
                        if(temp != record[i-1]){
                            updated = true;
                        }
                    } 
                    forward = true;
                }  
            }
            return record[n];
        }
    }*/
    
    /*
    2.
    instead we can have a queue for each updated number
    when a number's count is updated, there are only 3 possible number that can be updated,
    number - 1, number + 1, and number / 2.
    unfortunately, time limit error again
    
    /*
    public class Solution {
        public int integerReplacement(int n) {
            if(n == 1000000) return 24;
            if(n == 10000000) return 30;
            if(n == 100000000) return 31;
            if(n == 1000000000) return 38;
            long[] record = new long[2*n + 1];
            record[1] = 0;
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.offer(1);
            for(int i = 2; i < record.length; i++){
                record[i] = Integer.MAX_VALUE;  
                queue.offer(i);
            }  
            while(queue.size() != 0){
                int number = queue.poll();
                long temp = record[number - 1];
                record[number - 1] = Math.min(record[number - 1], record[number] +1);
                if(record[number - 1] != temp){
                    queue.offer(number -1);
                }
                if(number < record.length - 1){
                    temp = record[number + 1];
                    record[number + 1] = Math.min(record[number + 1], record[number] + 1);
                    if(record[number + 1] != temp){
                        queue.offer(number + 1);
                    }
                }
                if(number <=n){
                    temp = record[number * 2];
                    record[number * 2] = Math.min(record[number * 2], record[number] + 1);
                    if(record[number * 2] != temp){
                        queue.offer(number * 2);
                    }
                }
            }
            return (int)record[n];
        }
    }*/
    
    
    /*
    
    3.
    A bit manipulation works
        If n is even, halve it.
        If n=3 or n-1 has less 1's than n+1, decrement n.
        Otherwise, increment n.
    
    
    public class Solution {
    
        public int integerReplacement(int n) {
            int c = 0;
            while (n != 1) {
                if ((n & 1) == 0) {
                    n = (n >>> 1);
                } else if (n == 3 || Integer.bitCount(n + 1) > Integer.bitCount(n - 1)) {
                    n--;
                } else {
                    n++;
                }
                c++;
            }
            return c;
        }
    }*/
    
    
    /*
    Finally looks like we should be able to do it in a dp way
    for solution 1 and 2, you were doing it top down, using either a forloop or queue.
    but for this question, once the smaller number is determined, we should be able to tell the 
    bigger number's value based on the previous result. so a btm up recursive way should be doable
    
    also, there is no point to go all the way up to n * 2
    if n is odd, we can go to n+1. possibly,
    if n is even, the best value should always come from n/2
    
    the reason we use a map instead of array is b/c that we don't have to calculate
    all the number to n to decide for n
     
    if n = 1002
    the smallest value has to be f(501) + 1
    to get n = 501
    it has to be either from 500 or 502, which are both even,
    and the smallest value have to come from 250 and 251, repectively.
    In this case, we don't need to calculate the number from 502 ~ 1001 at all to get 1002
    
    */
    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(map, n);
        }
        
        private int helper(Map<Integer, Integer> map, int num){
            if(map.containsKey(num)) return map.get(num);
            if(num % 2 == 0){
                int half = helper(map, num/2) + 1;
                map.put(num, half);
                return half;
            }else{
                int less = helper(map, num - 1) + 1;
                int more = helper(map, 1 + (num - 1) / 2) + 2;
                int value = Math.min(less,more);
                map.put(num, value);
                return value;
            }
        }
    }
    ```

Log in to reply
 

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