blob: b46fc7882b387f05e0cd64e3be43b65692e1325b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class PrimitiveCalculator {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer> sequence = optimal_sequence(n);
System.out.println(sequence.size() - 1);
for (Integer x : sequence) {
System.out.print(x + " ");
}
}
public static List<Integer> optimal_sequence(int n) {
List<Integer> sequence = new ArrayList<Integer>();
int[] stepsCount = new int[n];
// the path int array indicates the next step to reduce it:
// 1: minus 1
// 2: divide by 2
// 3: divide by 3
int[] path = new int[n];
int div2Steps, div3Steps, minus1Steps;
for (int i = 1; i < stepsCount.length; i++) {
int j = i + 1;
div2Steps = Integer.MAX_VALUE;
div3Steps = Integer.MAX_VALUE;
if (j % 3 == 0) {
div3Steps = stepsCount[j / 3 - 1];
}
if (j % 2 == 0) {
div2Steps = stepsCount[j / 2 - 1];
}
minus1Steps = stepsCount[i - 1];
// I use a 2-dimensional array (3 by 2) as my data structure
// to determine steps and path to get to the current j. Inner
// 2-element array is the stepCount and path pair. This 2-dim
// array is then sorted by the first element of the pair
// (stepCount). This way the stepsCount and path arrays can be
// built up from 1 to n eventually.
int stepCountAndType[][] = { { minus1Steps, 1 }, { div2Steps, 2 }, { div3Steps, 3 } };
Arrays.sort(stepCountAndType, Comparator.comparingInt(arr -> arr[0]));
stepsCount[i] = stepCountAndType[0][0] + 1;
path[i] = stepCountAndType[0][1];
}
sequence.add(n);
while (n > 1) {
int i = path[n - 1];
if (i == 3) {
n = n / 3;
sequence.add(n);
continue;
}
if (i == 2) {
n = n / 2;
sequence.add(n);
continue;
}
n = n - 1;
sequence.add(n);
}
Collections.reverse(sequence);
return sequence;
}
public static List<Integer> greedy_sequence(int n) {
// Greedy algo is NOT safe, therefore won't produce
// the right results.
List<Integer> sequence = new ArrayList<Integer>();
while (n >= 1) {
sequence.add(n);
if (n % 3 == 0) {
n /= 3;
} else if (n % 2 == 0) {
n /= 2;
} else {
n -= 1;
}
}
Collections.reverse(sequence);
return sequence;
}
}
|
