จำนวนที่มีตัวประกอบเฉพาะเป็น 2, 3 หรือ 5 เรียกว่า จำนวนน่าเกลียด ตัวเลขที่น่าเกลียดบางส่วน ได้แก่ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15 เป็นต้น
เรามีตัวเลข N และภารกิจคือการหาเลขน่าเกลียดตัวที่ N ตามลำดับเลขน่าเกลียด
ตัวอย่างเช่น:
อินพุต-1:
N = 5
ผลลัพธ์:
5
คำอธิบาย:
เลขขี้เหร่ที่ 5 ตามลำดับเลขน่าเกลียด [1, 2, 3, 4, 5, 6, 8, 10, 12, 15] คือ 5
อินพุต-2:
N = 7
ผลลัพธ์:
8
คำอธิบาย:
เลขขี้เหร่ที่ 7 ตามลำดับเลขน่าเกลียด [1, 2, 3, 4, 5, 6, 8, 10, 12, 15] คือ 8
แนวทางในการแก้ปัญหานี้
วิธีง่ายๆ ในการแก้ปัญหานี้คือตรวจสอบว่าจำนวนที่กำหนดนั้นหารด้วย 2 หรือ 3 หรือ 5 ลงตัวหรือไม่ และติดตามลำดับจนถึงจำนวนที่กำหนด ตอนนี้ให้ค้นหาว่าตัวเลขตรงตามเงื่อนไขทั้งหมดของตัวเลขที่น่าเกลียดหรือไม่ จากนั้นให้ส่งคืนตัวเลขเป็นผลลัพธ์
- ป้อนข้อมูลตัวเลข N เพื่อค้นหาตัวเลขน่าเกลียดที่ N
- ฟังก์ชันบูลีน isUgly(int n) ใช้ตัวเลข 'n' เป็นอินพุตและส่งกลับค่า True หากเป็นตัวเลขที่น่าเกลียด มิฉะนั้นจะเป็นเท็จ
- ฟังก์ชันจำนวนเต็ม findNthUgly(int n) ใช้ตัวเลข 'n' เป็นอินพุตและส่งกลับ n ตัวเลขที่น่าเกลียดเป็นผลลัพธ์
ตัวอย่าง
public class UglyN {
public static boolean isUglyNumber(int num) {
boolean x = true;
while (num != 1) {
if (num % 5 == 0) {
num /= 5;
}
else if (num % 3 == 0) {
num /= 3;
}
// To check if number is divisible by 2 or not
else if (num % 2 == 0) {
num /= 2;
}
else {
x = false;
break;
}
}
return x;
}
public static int nthUglyNumber(int n) {
int i = 1;
int 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.
