Java DP Solution only with one loop


  • 0
    C
    class Solution {
        public int minSteps(int n) {
            if (n <= 0) return 0;
            int begin = n/2;
            int fract = 0;
            for (int i = begin; i>= 1; i--) {
                if (n%i == 0) {
                    fract += n/i;
                    n = i;
                }
            }
            return fract;
        }
    }
    

    example:

    input 8:
    8/4 = 2; fract += 2 = 2;
    4/2 = 2; fract += 2 = 4;
    2/1 = 2; fract += 2 = 6;

    input 9:
    9/3 = 3; fract += 3 = 3;
    3/1 = 3; fract += 3 = 6;


Log in to reply
 

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