Find the greatest common divisor (no DP)


  • 0
    Z

    The question is the same as finding the greatest common divisor.
    For 3: no common divisor greater or equal to 2, so the answer is 3.
    For 6: 6/3 = 2, so the answer is 2 + 3 = 5.
    For 24: 24/12 = 2, 12/6 = 2, 6/3 = 2, so the answer is 2 + 2 + 2 + 3 = 9.
    Here is the code:

    class Solution {
        public int minSteps(int n) {
            if (n == 1)
                return 0;
            int temp = n, ret = 0, i = 0;
            while (temp != 1 && i != 1) {
                for (i = temp / 2; i > 1; i--) {
                    if (temp % i == 0) {
                        ret += temp / i;
                        temp = i;
                        break;
                    }
                }
            }
            return ret + temp;
        }
    }
    

Log in to reply
 

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