C++ 3 ms 5 lines (prime numbers)


  • 2
    V

    We want to find the greatest divisor for our number, so we can minimize the number of steps by getting it in a buffer and pasting multiple times. The quickest way to find the greatest divisor is to start with the smallest prime and work our way up. Note that we only need primes up to 31 as n is limited to 1,000 (32 * 32 > 1,000).

    When we find a prime i, the greatest divisor will be n / i. Then, we will recursively calculate the minimum steps for that greatest divisor.

    int minSteps(int n) {
        static const int primes[11] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
        if (n <= 5) return n == 1 ? 0 : n;
        for (auto i : primes)
            if (n % i == 0) return i + minSteps(n / i);
        return n; // prime number.
    }
    

  • 1

    @votrubac 100 * 100 = 10000, n / (n / i) = i


  • 0
    V

    @mzchen Oh.. thanks, missed a zero! I updated the solution and description accordingly. And thanks for the simplification... I need to pay more attention and check/clean up the debug code :)


Log in to reply
 

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