```
int nthUglyNumber1(int n) // Score 16ms
{
int result = 1; // For the case n = 1
if (n > 1)
{
vector<int> u(n,0);
u[0] = 1;
int c1,c2,c3; // 3 candidates corresponding to the three factors 2, 3, 5
int i1 = 0, i2 = 0, i3 = 0;
int a[3] = {2,3,5};
c1 = a[0]*u[i1]; c2 = a[1]*u[i2]; c3 = a[2]*u[i3]; // 3 candidates, initialized
int i,j,cmin;
for (i = 1; i < n; i++)
{
// Find the minimum from c2, c3, c5
cmin = c1; j = a[0]; // 2
if (cmin > c2) { cmin = c2; j = a[1]; } // 3
if (cmin > c3) { cmin = c3; j = a[2]; } // 5
while (cmin == u[i-1]) // Checking this condition is to prevent duplication
{
// Update one of the three candidates
if (j == a[0]) { i1++; c1 = a[0]*u[i1]; }
if (j == a[1]) { i2++; c2 = a[1]*u[i2]; }
if (j == a[2]) { i3++; c3 = a[2]*u[i3]; }
// Find the minimum from c2, c3, c5 again
cmin = c1; j = a[0]; // 2
if (cmin > c2) { cmin = c2; j = a[1]; } // 3
if (cmin > c3) { cmin = c3; j = a[2]; } // 5
}
u[i] = cmin;
}
result = u[n-1];
}
return (result);
}
```