Ugly number I and II

Posted by chunyang on February 25, 2020

Ugly numbers are numbers which only divided by 2, 3, 5. By default 1 is also a ugly number.

Ugly Number I

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6

Output: true

Explanation: 6 = 2 × 3

Example 2:

Input: 8

Output: true

Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14

Output: false

Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

  • 1 is typically treated as an ugly number.
  • Input is within the 32-bit signed integer range: [−231, 231 − 1].

Just implement it according to definitions.

// 263. Ugly Number
// https://leetcode.com/problems/ugly-number/

class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0) return false;
        while (num % 6 == 0) num /= 6;
        while (num % 10 == 0) num /= 10;
        while (num % 15 == 0) num /= 15;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
};

Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10

Output: 12

Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

  • 1 is typically treated as an ugly number.
  • n does not exceed 1690.

Directly test each number until we get enough number is one of the brute-force method.

We can expect a TLE.

class Solution {
public:
    bool isUglyNumber(int num) {
        if (num <= 0) return false;
        while (num % 6 == 0) num /= 6;
        while (num % 10 == 0) num /= 10;
        while (num % 15 == 0) num /= 15;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;

    }
    int nthUglyNumber(int n) {
        int cnt = 0;
        int i = 1;
        while (cnt < n) {
            if (isUglyNumber(i)) ++cnt;
            ++i;
        }
        return i-1;
    }
};

Each ugly number comes from a smaller ugly number multiplied by 2, 3, 5. So we can use three pointers to point to previous smaller number so far.

// 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> l(n);
        vector<int> p{0};
        l[0] = 1;
        for (int i = 1; i < n; ++i) {
            l[i] = min({l[p[0]] * 2, l[p[1]] * 3, l[p[2]] * 5});
            if (l[p[0]] * 2 == l[i]) ++p[0];
            if (l[p[1]] * 3 == l[i]) ++p[1];
            if (l[p[2]] * 5 == l[i]) ++p[2];
        }
        return l[n - 1];
    }
};

Summary

It is a little like the prime test problem. To tell whether a number is a prime, we can directly test it or use sieve algorithm. But actually they are used under different situations.


Creative Commons License
This work is licensed under a CC A-S 4.0 International License.