Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement: Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.
If there are multiple answers, print any of them.
Example 1:
Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.
Example 2:
Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactlyn 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
Example 1:
Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
int minSteps(int n) {
if (n == 1) return0;
int res = n;
for (int i = n - 1; i > 1; --i) {
if (n % i == 0) {
res = min(res, minSteps(n / i) + i);
}
}
return res;
}
int minSteps(int n) {
vector<int> dp(n + 1, 0);
for (int i = 2; i <= n; ++i) {
dp[i] = i;
for (int j = i - 1; j > 1; --j) {
if (i % j == 0) {
dp[i] = min(dp[i], dp[j] + i / j);
}
}
}
return dp[n];
}
下面我们来看一种省空间的方法，我们不需要记录每一个中间值，而是通过改变n的值来实时累加结果res
int minSteps(int n) {
int res = 0;
for (int i = 2; i <= n; ++i) {
while (n % i == 0) {
res += i;
n /= i;
}
}
return res;
}
2 * 2 = 2 + 2; 2 * 3 > 2 + 3; 4 * 4 > 4 + 4; so it is always better to divide whenever possible.
now it became a problem for finding all possible factors;
The essence is so it is always better to divide whenever possible
* It take 2 op to double, 3 ops to triple, ...
* if n % 2 == 0, then f(n) = f(n/2) + 2
* if n % 3 == 0, then f(n) = f(n/3) + 3
* 2 * 2 = 2 + 2, 2 * 3 > 2 + 3, 4 * 4 > 4 + 4, so it is always better to divide whenever possible.
* now it became a problem for finding all possible factors;
intminSteps(int n) {
if (n == 1) return0;
for (int i = 2; i < n; i++)
if (n % i == 0) return i + minSteps(n / i);
return n;
}
int minSteps(int n) {
if (n == 1) return 0;
vector<int> dp(n+1, 0);
// dp[1] = 1;
dp[2] = 2;
return dfs(dp, n);
}
int dfs(vector<int>&dp, int x) {
if (dp[x] ) return dp[x];
int ans = x;
for (int i = 2; i <= sqrt(x); i++) {
if (x % i == 0) {
ans = min( ans, dfs(dp, x/i) + i );
ans = min( ans, dfs(dp, i) + x/i );
}
}
dp[x] = ans;
return dp[x];
} https://blog.csdn.net/TheSnowBoy_2/article/details/76722359
两种操作使得问题变得较为简单，因为状态空间因此被简化了。
We can break our moves into groups of (copy, paste, ..., paste). Let C denote copying and Pdenote pasting. Then for example, in the sequence of moves CPPCPPPPCP, the groups would be [CPP][CPPPP][CP].
Say these groups have lengths g_1, g_2, .... After parsing the first group, there are g_1'A's. After parsing the second group, there are g_1 * g_2'A's, and so on. At the end, there are g_1 * g_2 * ... * g_n'A's.
We want exactly N = g_1 * g_2 * ... * g_n. If any of the g_i are composite, say g_i = p * q, then we can split this group into two groups (the first of which has one copy followed by p-1 pastes, while the second group having one copy and q-1 pastes).
Such a split never uses more moves: we use p+q moves when splitting, and pq moves previously. As p+q <= pq is equivalent to 1 <= (p-1)(q-1), which is true as long as p >= 2 and q >= 2.
Algorithm By the above argument, we can suppose g_1, g_2, ... is the prime factorization of N, and the answer is therefore the sum of these prime factors.
Time Complexity: O(N). When N is the square of a prime, our loop does O(N) steps.
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.
publicint minSteps(int n) {
int s = 0;
for (int d = 2; d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s;
}
Point 1: the whole steps will be like this: CP..P CP..P CP..P. So in each segment, it's always like oneC with >=1's P. The answer is the length of this character array.
Point 2: once you reach to a non-divisor of n at the end of any segment, it's impossible to reach n anymore. The reason is: once you reach y at the end of segment, then all future operations lead to a number that is a multiple of y, but n is not a multiple of y, so it's impossible to reach n. This means you have to make sure that each segment leads to a number that is a divisor of n.
Point 3: there are many divisors to choose, which include n itself (corresponding to CPPP..PPP array with n-1P). The best solution must choose one of them. Here we say the best solution always choose divisor that is not the special divisor n, because compared to the special divisor n, there is always a better divisor y to choose where 1<y<=sqrt(n) (if such y exists). If we choose n, then the length is one C and n-1P so length is n. If we choose y where 1<y<=sqrt(n), then the length is at most y + (n / y) because there is at least one solution CPP..P CPP..P with first segment y-1 number of P, and second segment n/y - 1 number of P. With y's constraint, after some steps, we can see this length is always <=n. So if such y exists, then the best solution will choose one such y. This is the only "optimizing" step in the whole proof.
Point 4: we will reach to a point that it's always best to choose a prime divisor because non-prime divisor will continue the above process until no such y exists, or n becomes prime number.
Point 5: so the best solution must begin with a segment that leads to a prime divisor of n. For example, if n is 60, then the best solution either begins with a segment that reaches 2, or begins with a segment that reaches 3, or 5.
Point 6: once you reach to a divisor y through steps A=CP...P, then we just do new_n = n/y because we can attach array A as prefix to the array of new_n's solution array.
Point 7: with the above point, then the whole solution array of n is like this: one segment that reaches one prime divisor y, get a new n from n/y, then get another segment that reaches one prime divisor w (probably w=y), and get a new n.
Point 8: segment's order does not matter. CPPCPPPP reaches to the same number with CPPPPCPP.
Point 9: so then you will realize that the solution is like this. If n's prime factorization is p^a * q^b * r^c where p q r are prime divisors of n, then the whole array is one permutation of the segment array: a number of segment-1 "CPP...P" with p-1P, b number of segment-2 "CPP..P" with q-1P, c number of segment-3 "CPP..P" with r-1P. So the whole solution is: a*p + b*q + c*r.
Point 10: the given solution in this discussion thread is always beginning from smallest prime divisor, which makes it look like a greedy solution, but that we know it's a greedy solution gives us little value, because the correctness proof lies in prime factoring.
To get the DP solution, analyse the pattern first by generating first few solutions
1: 1
2: 2
3: 3
4: 4
5: 5
6: 5
7: 7
8: 6
9: 6
10: 7
11: 11
12: 7
13: 13
14: 14
15: 8
Now, check the solution.
Eg: n=6
To get 6, we need to copy 3 'A's two time. (2)
To get 3 'A's, copy the 1 'A' three times. (3)
So the answer for 6 is 5
Now, take n=9.
We need the lowest number just before 9 such that (9% number =0). So the lowest number is 3.
So 9%3=0. We need to copy 3 'A's three times to get 9. (3)
For getting 3 'A's, we need to copy 1 'A' three times. (3)
So the answer is 6
Finally to analyse the below code, take n=81.
To get 81 we check
if (81 % 2 ==0) No
if (81 % 3 ==0) Yes
So we need to copy 81/3 = 27 'A's three times (3)
Now to get 27 'A's, we need to copy 27/3= 9 'A's three times (3)
To get 9 'A's, we need to copy 9/3=3 'A's three times (3)
And to get 3 'A's, we need to copy 3/3=1 'A's three times (3)
Final answer is 3+3+3+3 = 12
Last Example, n=18
18/2 = 9 Copy 9 'A's 2 times (2)
9/3=3 Copy 3 'A's 3 times (3)
3/3=1 Copy 1'A's 3 times (3)
Answer: 2+3+3= 8
publicintminSteps(int n){
int res = 0;
for(int i=2;i<=n;i++){
while(n%i == 0){
res+= i;
n=n/i;
}
}
return res;
}
