forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNthUglyNumber.java
More file actions
80 lines (69 loc) · 2.72 KB
/
NthUglyNumber.java
File metadata and controls
80 lines (69 loc) · 2.72 KB
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
package com.thealgorithms.maths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
/**
* @brief class computing the n-th ugly number (when they are sorted)
* @details the ugly numbers with base [2, 3, 5] are all numbers of the form 2^a*3^b^5^c,
* where the exponents a, b, c are non-negative integers.
* Some properties of ugly numbers:
* - base [2, 3, 5] ugly numbers are the 5-smooth numbers, cf. https://oeis.org/A051037
* - base [2, 3, 5, 7] ugly numbers are 7-smooth numbers, cf. https://oeis.org/A002473
* - base [2] ugly numbers are the non-negative powers of 2,
* - the base [2, 3, 5] ugly numbers are the same as base [5, 6, 2, 3, 5] ugly numbers
*/
public class NthUglyNumber {
private ArrayList<Long> uglyNumbers = new ArrayList<>(Arrays.asList(1L));
private final int[] baseNumbers;
private HashMap<Integer, Integer> positions = new HashMap<>();
/**
* @brief initialized the object allowing to compute ugly numbers with given base
* @param baseNumbers the given base of ugly numbers
* @exception IllegalArgumentException baseNumber is empty
*/
NthUglyNumber(final int[] baseNumbers) {
if (baseNumbers.length == 0) {
throw new IllegalArgumentException("baseNumbers must be non-empty.");
}
this.baseNumbers = baseNumbers;
for (final var baseNumber : baseNumbers) {
this.positions.put(baseNumber, 0);
}
}
/**
* @param n the zero-based-index of the queried ugly number
* @exception IllegalArgumentException n is negative
* @return the n-th ugly number (starting from index 0)
*/
public Long get(final int n) {
if (n < 0) {
throw new IllegalArgumentException("n must be non-negative.");
}
while (uglyNumbers.size() <= n) {
addUglyNumber();
}
return uglyNumbers.get(n);
}
private void addUglyNumber() {
uglyNumbers.add(computeMinimalCandidate());
updatePositions();
}
private void updatePositions() {
final var lastUglyNumber = uglyNumbers.get(uglyNumbers.size() - 1);
for (final var baseNumber : baseNumbers) {
if (computeCandidate(baseNumber) == lastUglyNumber) {
positions.put(baseNumber, positions.get(baseNumber) + 1);
}
}
}
private long computeCandidate(final int candidateBase) {
return candidateBase * uglyNumbers.get(positions.get(candidateBase));
}
private long computeMinimalCandidate() {
long res = Long.MAX_VALUE;
for (final var baseNumber : baseNumbers) {
res = Math.min(res, computeCandidate(baseNumber));
}
return res;
}
}