Check whether a Number is a Smith Number in Java

Topic

A Smith Number is a composite number whose sum of digits equals the sum of the digits of its prime factors (excluding 1 and the number itself).

For example, 666 is a Smith number because:

Sum of digits = 6 + 6 + 6 = 18
Prime factorization of 666 = 2 × 3 × 3 × 37
Sum of digits of prime factors = 2 + 3 + 3 + (3 + 7) = 18

This problem tests your understanding of number decomposition, digit sum calculation, and factorization using loops.

Examples

Example 1:

Input: 666
Output: true
Explanation: Sum of digits = 6+6+6 = 18,
Prime factors = 2, 3, 3, 37 → digit sum = 2+3+3+(3+7)=18

Example 2:

Input: 27
Output: false
Explanation: Sum of digits = 2+7 = 9,
Prime factors = 3, 3, 3 → digit sum = 3+3+3 = 9 (equal),
But 27 is not composite enough for standard Smith criteria (can be disputed), better to test with 666.

Example 3:

Input: 13
Output: false
Explanation: 13 is a prime number, and Smith numbers are defined only for composite numbers.

Interviewer Expectations

Ability to use loops and conditionals to check prime and factor logic
Understanding of digit-sum logic
Clean decomposition of problems into smaller reusable methods
Understanding of number theory basics

Approach

Check if the number is prime — if yes, return false
Calculate the sum of digits of the original number
Find all prime factors (with multiplicity), and calculate the sum of digits of all prime factors
Compare both sums — if equal, it’s a Smith number

Dry Run (for 666)

Sum of digits: 6 + 6 + 6 = 18
Prime factors: 2, 3, 3, 37 → digit sum: 2 + 3 + 3 + 3 + 7 = 18
Result: 18 == 18 → true

Java Program

public class SmithNumber {
    public static void main(String[] args) {
        int number = 666;
        if (isPrime(number)) {
            System.out.println(false);
            return;
        }

        int originalDigitSum = digitSum(number);
        int factorDigitSum = 0;
        int n = number;

        for (int i = 2; i <= n; i++) {
            while (n % i == 0) {
                if (isPrime(i)) {
                    factorDigitSum += digitSum(i);
                    n /= i;
                } else {
                    break;
                }
            }
        }

        System.out.println(originalDigitSum == factorDigitSum);
    }

    static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    static int digitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

true

Possible Followup Questions with Answers

What are some other special numbers similar to Smith Numbers?

Other classifications include Armstrong numbers, Harshad numbers, Kaprekar numbers, etc. These also involve digit manipulations and checks.

Can Smith Numbers be negative?

No, Smith numbers are only defined for positive integers, specifically composite numbers.

What if the number is a large integer like 99999991?

If the number is prime, the function will return false. If composite, it will still work — just slower. You can optimize by precomputing primes or using Sieve of Eratosthenes for large ranges.

Can we optimize factorization further?

Yes. Use prime caching, skip even numbers after 2, or check up to √n only.

⬅ Previous TopicCheck Whether a Number is a Spy Number in Java

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

Comments

Loading comments...