Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/ugly-number/
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Một số được gọi là Số xấu khi số đó là một số nguyên dương có thừa số nguyên tố là 2, 3 và 5.
Cho một số nguyên n, trả về kết quả là true nếu n là Số xấu.
Điều kiện:
-2^31 <= n <= 2^31 - 1.
Ví dụ 1:
Input: n = 6
Output: true
Explanation: 6 = 2 × 3
Ví dụ 2:
Input: n = 1
Output: true
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Ví dụ 3:
Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.
3. Phân tích
Bài này hơi liên quan đến toán một chút. Như các bạn đã biết số nguyên tố là số chỉ chia hết cho 1 và chính nó. Và trong bài này, chúng ta cần kiểm tra xem số đó có chứa thừa số nguyên tố là 2, 3 và 5 không.
Để làm được bài này chúng ta cần làm rõ với nhau rằng số n chỉ được chứa thừa số nguyên tố là 2, 3 và 5 mà thôi. Ví dụ như số 14 = 2 x 7, cũng có hai thừa số nguyên tố là 2 và 7 nhưng đề bài chỉ giới hạn cho chúng ta ba số nguyên tố nhỏ hơn hoặc bằng 5.
Giờ hãy đọc lại đê bài: số xấu là số nguyên dương, tuy nhiên điều kiện dữ liệu đầu vào thì n lại có cả số âm. Như vậy ta có thể đặt điều kiện loại trừ nếu n <= 0 thì trả về false luôn.
Ý tưởng để giải bài này cũng đơn giản, chúng ta sẽ kiểm tra n có chia hết cho lần lượt các số 2, 3 và 5 không. Nếu thỏa mãn điều kiện của trường hợp nào, ta lấy n chia cho số đó và gán giá trị sau khi đã chia cho n. Ta cứ làm vậy đến khi n giảm xuống còn 1, điều này có nghĩa n chỉ chứa các thừa số nguyên tố là 2, 3 và 5 chứ không chứa bất kì thừa số nguyên tố nào khác.
Ok! Hãy cùng xem code chạy như thế nào nhé!
4. Code chạy bằng cơm
Như phân tích ở trên, ta sẽ phải làm một công việc lặp đi lặp lại, ấy là kiểm tra và chia n cho các thừa số nguyên tố 2, 3 và 5. Vậy thì ta sẽ làm một cái vòng lặp while() với điều kiện là n > 1, bởi vì nếu n là số xấu thì nó phải giảm về được 1, khi đó ta sẽ dừng vòng lặp.
Hãy thử lấy ví dụ với n = 60 nhé. Đầu tiên chúng ta sẽ kiểm tra xem n có chia hết cho 2 không:
Tiếp tục lại kiểm tra ta lại thấy chia hết cho 2:
Tiếp ta thấy khi này n chia hết cho 3:
Khi này n vẫn lớn hơn 1 nên ta tiếp tục kiểm tra và gán giá trị cho n như trên:
Tới đây thì n = 1, vậy là n không chứa thừa số nguyên tố nào ngoài ba số trên. Trả về true là xong, nếu không thực hiện được các bước trên thì n không phải số xấu, trả về false thôi ạ.
5. Code chạy bằng máy
Code của chúng ta sẽ như sau:
public boolean isUgly(int n) {
while (n > 1) {
if (n % 2 == 0) {
n /= 2;
} else if (n % 3 == 0){
n /= 3;
} else if (n % 5 == 0){
n /= 5;
} else{
return false;
}
}
return n > 0;
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận