หา Ugly Number ตัวที่ N ใน Java

Ugly Number คืออะไร?

จำนวนที่เฉพาะตัวประกอบ (Prime Factors) มีแค่ 2, 3, 5 เท่านั้น
ลำดับ: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

ตัวอย่าง

Input: N = 5

Output: 5 (Ugly number ตัวที่ 5 คือ 5)

Input: N = 7

Output: 8 (Ugly number ตัวที่ 7 คือ 8)

แนวทางแก้ปัญหา (Simple)

• ตรวจสอบแต่ละตัวเลขว่าหาร 2, 3, 5 ลงตัวจนเหลือ 1
• นับจำนวน Ugly numbers จนครบ N
• ฟังก์ชัน isUglyNumber(num): หาร 5, 3, 2 ตามลำดับ จนไม่หารลงตัว ถ้าเหลือ 1 = Ugly
• ฟังก์ชัน nthUglyNumber(n): วนลูป i=1,2,3... นับ Ugly จนครบ n

ตัวอย่างโค้ด Java

public class UglyN {
    public static boolean isUglyNumber(int num) {
        while (num != 1) {
            if (num % 5 == 0) num /= 5;
            else if (num % 3 == 0) num /= 3;
            else if (num % 2 == 0) num /= 2;
            else return false;
        }
        return true;
    }

    public static int nthUglyNumber(int n) {
        int i = 1, count = 1;
        while (n > count) {
            i++;
            if (isUglyNumber(i)) count++;
        }
        return i;
    }

    public static void main(String[] args) {
        int number = 100;
        int no = nthUglyNumber(number);
        System.out.println("The Ugly no. at position " + number + " is " + no);
    }
}

ผลลัพธ์

The Ugly no. at position 100 is 1536.

หมายเหตุ

วิธีนี้ช้า (O(N log N)) สำหรับ N ใหญ่ ควรใช้ Dynamic Programming (3 pointers) ซึ่งเป็น O(N) แทน