Loop best case log(n), no DP, no extra space, no recursion, with explanation

• We look for a divisor `d` so that we can make `d` copies of `(n / d)` to get `n`

The process of making `d` copies takes `d` steps (`1` step of Copy All and `d - 1` steps of Paste)

We keep reducing the problem to a smaller one in a loop.

The best cases occur when `n` is decreasing fast, and method is almost `O(log(n))`

For example, when `n = 1024` then `n` will be divided by `2` for only `10` iterations, which is much faster than `O(n)` DP method.

The worst cases occur when `n` is some multiple of large prime, e.g. `n = 997` but such cases are rare.

``````    public int minSteps(int n) {
int s = 0;
for (int d = 2; d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s;
}
``````

• @yuxiangmusic did this actually pass all tests?

• @c8b2b9ef It does - had the same solution.

• As n <= 1000, this method is not taking much more time than the DP solution. In which case, DP has to loop from 1 to n.

• Ruby version.

``````require 'prime'

def min_steps(n)
n.prime_division.map { |p, e| p * e }.sum
end
``````

• If add an if case, in the for loop, go from 2 to sqrt(n) is enough. The codes are as follows

``````public int minSteps(int n) {
int s = 0;
for (int d = 2; d <= Math.sqrt(n); d++) {
while (n % d == 0) {
s += d;
n /= d;
}

}
if (n!=1){
s+=n;
}
return s;
}
``````

• This is greedy approach, am i right?

• This post is deleted!

• I think this is greedy algorithm. Can anyone prove this algorithm is correct?

• whats the complexity for worst case ? o(n) ?

• whats the complexity for worst case ? o(n) ?

No, O(n).

• This is not real O(lg(n)) solution! It's O(n) on average

A much faster solution is:

``````public int minSteps(int n) {
// list of primes that are not greater than SQRT(n) - in this case, n = 1000,000, SQRT(n) = 1000
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
int ans = 0;
for (int p : primes) {
while ((n % p) == 0) {
ans += p;
n /= p;
}
}
return ans + (n == 1 ? 0 : n);
}
``````

To show the difference:

``````public class TwoKeysKeyboard650 {
public int minSteps(int n) {
// list of primes that are not greater than SQRT(n) - in this case, n = 1000,000
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
int ans = 0;
for (int p : primes) {
while ((n % p) == 0) {
ans += p;
n /= p;
}
}
return ans + (n == 1 ? 0 : n);
}

public int minSteps1(int n) {
int s = 0;
for (int d = 2; d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s;
}

static public void main(String[] args) {
TwoKeysKeyboard650 test = new TwoKeysKeyboard650();
long max = 0l;
for (int i = 1; i < 1000000; i++) {
long start = System.currentTimeMillis();
test.minSteps(i);
// test.minStep1(i);
max = Math.max(max, System.currentTimeMillis() - start);
}
System.out.println(max);
}
}
``````

• You can just change

`````` for (int d = 2; d <= n; d++) {
``````

to

`````` for (int d = 2; d * d <= n; d++) {
``````

and add the remains in the end if the remains not equal to 1

which makes the worst case complexity down to O(N ** 1/2)

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