[Leetcode] 263. Ugly Number - Java

https://leetcode.com/problems/ugly-number/description/

Ugly Number - LeetCode

---

문제

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

 

Example 1:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 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.

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

 

Constraints:

• -231 <= n <= 231 - 1

---

풀이

풀이 과정

ugly number란 자연수 중 2, 3, 5만을 소인수로 가진 수를 의미한다.

문제에서 주어지는 n의 범위는 -2³¹ <= n <= 2^{31 - 1} 이므로 우선 음수일 경우는 제외한다.

class Solution {
    public boolean isUgly(int n) {
        if(n < 1) return false;
}

 

이후 n을 2, 3, 5로 나머지가 0이 되지 않을 때 까지 나누어 최종적으로 남은 수가 1이 아니라면 2, 3, 5이외에 다른 약수가 존재하는 것이므로 false를 반환하고 아니라면 true를 반환한다.

boolean answer = true;
/*
 * 2, 3, 5로 나누어 떨어지지 않을 때까지 차례대로 n을 나눔
 *
 */
while(n % 2 == 0){ n /= 2; };
while(n % 3 == 0){ n /= 3; };
while(n % 5 == 0){ n /= 5; };

// 모두 나누고 남은 수가 1이 아니라면 다른 약수가 존재
if(n != 1) answer = false;

return answer;

---

최종 코드

class Solution {
    public boolean isUgly(int n) {
        if(n < 1) return false;
        
        boolean answer = true;
        /*
         * 2, 3, 5로 나누어 떨어지지 않을 때까지 차례대로 n을 나눔
         *
         */
        while(n % 2 == 0){ n /= 2; };
        while(n % 3 == 0){ n /= 3; };
        while(n % 5 == 0){ n /= 5; };

        // 모두 나누고 남은 수가 1이 아니라면 다른 약수가 존재
        if(n != 1) answer = false;

        return answer;
    }
}

---