Check whether a number is a Hamming number in Java

Topic

A Hamming number is a positive number that has no prime factor other than 2, 3, or 5. These are also known as Ugly Numbers.

In simpler terms, a number is a Hamming number if it can be completely divided (factorized) using only 2, 3, or 5.

For example, 30 is a Hamming number because 30 = 2 × 3 × 5, but 14 is not, because it has 7 as a prime factor.

Examples

Input: 30
Output: true
Explanation: 30 = 2 × 3 × 5

Input: 1
Output: true
Explanation: By definition, 1 is considered a Hamming number.

Input: 14
Output: false
Explanation: 14 = 2 × 7 → 7 is not allowed (only 2, 3, 5 allowed)

Interviewer Expectations

In this question, the interviewer wants to check if you understand:

Basic loop and condition handling in Java
Prime factorization using division
Handling edge cases like 0 and 1

The logic is straightforward but helps evaluate how clearly you think through conditions and edge cases.

Approach

We can repeatedly divide the number by 2, 3, and 5 as long as it is divisible by those numbers. After all the divisions, if the number becomes 1, it's a Hamming number. Otherwise, it's not.

Dry Run

Input: 60
Step 1: 60 divisible by 2 → 60 / 2 = 30
Step 2: 30 divisible by 2 → 30 / 2 = 15
Step 3: 15 divisible by 3 → 15 / 3 = 5
Step 4: 5 divisible by 5 → 5 / 5 = 1
Final Result: 1 → YES, it's a Hamming number

Java Program

public class HammingNumberChecker {
    public static void main(String[] args) {
        int number = 30;
        boolean result = isHammingNumber(number);
        System.out.println(number + " is a Hamming number? " + result);
    }

    public static boolean isHammingNumber(int num) {
        if (num <= 0) return false;

        int[] primes = {2, 3, 5};
        for (int p : primes) {
            while (num % p == 0) {
                num /= p;
            }
        }
        return num == 1;
    }
}

30 is a Hamming number? true

Possible Followup Questions with Answers

1. What is the time complexity of this solution?

The time complexity is O(log N) in the worst case since the number is divided by its prime factors repeatedly.

2. What are other names for Hamming numbers?

They are also called Ugly Numbers in programming contexts.

3. How would you find the N^th Hamming number?

You can use dynamic programming or a min-heap to generate Hamming numbers in order and return the N^th one.

4. Can we generalize this to any set of allowed prime factors?

Yes! You can pass an array of allowed primes and follow the same approach by dividing the number using those primes only.

public static boolean isSpecialHamming(int num, int[] allowedPrimes) {
    for (int p : allowedPrimes) {
        while (num % p == 0) num /= p;
    }
    return num == 1;
}

⬅ Previous TopicJava Interview Program - Check Whether a Number is a Harshad (Niven) Number

Next Topic ⮕Check Whether a Number is a Spy Number in Java

Comments

Loading comments...