# Java Solution by Binary Search

• use an array to hold the ugly numbers, suppose at ith position and the current number is x; so the next number must be some number, say y, which is less than x, but 2 * y or 3 * y or 5 *y just greater than x;
The difficulty here is how to find the y; if just go through from 0/1 to i, the algorithm will end up O(n * n); I just noticed that the numbers before i is actually sorted. so I can use binary search, the search target is actually x / 2, x / 3 and x / 5;

following is the code:

``````public int nthUglyNumber(int n) {
if (n <= 5) {
return n;
}
int[] zs = {2, 3, 5};
int[] nums = new int[n + 1];
int i = 1;
for (; i <= 5; i++) {
nums[i] = i;
}
int x = 5;

while (i <= n) {
int nextMin = Integer.MAX_VALUE;
for (int z : zs) {
int y = x / z;
int j = nextPosGe(nums, y, 1, i);
while (nums[j] * z <= x) {
j = j + 1;
}
nextMin = Math.min(nextMin, nums[j] * z);
}
x = nextMin;
nums[i] = x;
i += 1;
}

return nums[n];
}

private int nextPosGe(int[] nums, int y, int start, int end) {
int i = start, j = end - 1;
while (i <= j) {
int mid = (i + j) / 2;
if (nums[mid] < y) {
i = mid + 1;
} else {
j = mid - 1;
}
}
return i;
}``````

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