Armstrong Number Validator

Question

Purpose

Validate if a number is an Armstrong Number.

An Armstrong Number is a number

such that the sum of the cubes of its digits is equal to the number itself. For example, 371 is an Armstrong number since 3³ + 7³ + 1³ = 371.

Strategy

• Calculate the remainder and quotient of the candidate value.
• While the quotient is greater than 0 and the digit sum is not greater than the candidate value, calculate the new remainder, the new quotient, and add remainder raised by 3 to the digit sum.

Implementation

public class ArmstrongNumberValidatorImpl implements ArmstrongNumberValidator {
    @Override
    public boolean isArmstrong(final long candidate) {
        if (candidate < 0) {
            throw new IllegalArgumentException("candidate value must be non-negative");
        }

        long remainder = candidate % 10;
        long quotient = candidate / 10;
        long digitSum = Math.multiplyExact(Math.multiplyExact(remainder, remainder), remainder);
        while (quotient > 0 && digitSum <= candidate) {
            remainder = quotient % 10;
            quotient = quotient / 10;
            digitSum += Math.multiplyExact(Math.multiplyExact(remainder, remainder), remainder);
        }

        return (0 == quotient && digitSum == candidate);

    }
}

Answer 1

Why use multiplyexact?

I'm puzzled why you wrote this:

digitSum += Math.multiplyExact(Math.multiplyExact(remainder, remainder), remainder);

instead of this:

digitSum += remainder * remainder * remainder;

You already know that remainder is a single digit value so computing the cube of it will never overflow.

Extraneous check

Your final return statement could be reduced from this:

return (0 == quotient && digitSum == candidate);

to this:

return (digitSum == candidate);

Your while loop will only terminate on this condition:

quotient == 0 || digitSum > candidate

which means that when digitSum == candidate, quotient must always be 0.

Answer 2

I am not too much of a Java expert, but I believe a do-while loop would be more readable here.

Instead of:

    long remainder = candidate % 10;
    long quotient = candidate / 10;
    long digitSum = Math.multiplyExact(Math.multiplyExact(remainder, remainder), remainder);
    while (quotient > 0 && digitSum <= candidate) {
        remainder = quotient % 10;
        quotient = quotient / 10;
        digitSum += Math.multiplyExact(Math.multiplyExact(remainder, remainder), remainder);
    }

You can do:

    long quotient = candidate;
    long remainder, digitSum = 0;
    do {
        remainder = quotient % 10;
        quotient = quotient / 10;
        digitSum += Math.multiplyExact(Math.multiplyExact(remainder, remainder), remainder);
    } while (quotient > 0 && digitSum <= candidate);

Answer 3

As soon as I saw the first line of your code, I was pretty sure that I recognized the distinctive signature of your work. Why is there an interface and a BlahBlahImpl? Why isn't the solution just a static function? Why does the parameter need to be final?

Your definition of an Armstrong number is not general enough — it is correct only for three-digit numbers. For an n-digit number, you're supposed to raise each digit to the n^th power. (You can easily see that by your criterion, there can be no matches with five or more digits: 9³ + 9³ + 9³ + 9³ + 9³ = 3645. In fact, there are no matches with four digits either.) For the purposes of this review, I'll stick with your wrong definition.

I'm not convinced that a negative input should trigger an IllegalArgumentException. Just based on the definition, I'd say that false is a perfectly fine answer.

The logic can be simplified, especially in light of the observations above.

public class ArmstrongTester {
    public static boolean isArmstrong(long n) {
        for (long q = n; n >= 0 && q > 0; q /= 10) {
            long digit = q % 10;
            n -= digit * digit * digit;
        }
        return n == 0;
    }
}

Answer 4

Simplification

• You can simplify your return condition. When you break from your loop it is either because the quotient equals 0 or the digit sum is greater than the candidate number. If the quotient is nonzero then the digit sum must be greater than the candidate. Therefore, all you need to do is return (digitSum == candidate).

Math

• As is mentioned in another answer there is no need for multiplyExact. Even a 10-bit number can store the result of any cubed digit. So unless your long is less than 10-bit you should be ok.

• My first thought would be maybe we need addExact not multiplyExact. However we can show that addExact is most likely not needed either. We can always represent the candidate within a long by definition. Let \$n\$ represent this candidate value. The question we need to answer is when is the digit sum greater than \$n\$, i.e. when is there a chance for us to overflow the long when performing the digit sum?

  This question isn't so easy to answer. But we can answer an easier question: When does a \$m\$-digit number have at most an \$m-1\$ digit cube digit sum?

  The best case is that the \$m\$-digit number is composed only of \$9\$.

  $$ m \cdot 9^3 \leq 10^{m-1} - 1$$ $$ 9^3 \leq \frac{10^{m-1} - 1}{m}$$

  The right side of the inequality is monotonically increasing on \$[1, \infty)\$ in both the continuous and discrete domain. In the discrete world, you can see this by changing the value from \$m=i\$ to \$m=i+1\$ which increases the numerator by more than 10 and the denominator by at most 2. Anyway, we get equality if \$m \approx 4.51778\$. So for any number with 5 or more digits, the sum cannot overflow. The same argument shows that any number with 5 or more digits cannot satisfy your definition of an Armstrong number either.

Performance

Scalability is always what I look for in problems like this. Yes a long may not be that big these days but why limit ourselves with inferior algorithms that do not scale well? Consider you have the number $$n = 123456789012345678901234567890...$$

Let's just say this number has \$m\$ digits. You will end up performing \$2m\$ multiplications and \$m-1\$ additions. However, of those multiplications, you can only have \$10\$ unique values since there are only \$10\$ digits. You should therefore pre-compute the powers so that you do not have to recompute them over and over.

final static long[] cubes = { 0, 1, 8, 27, 64, 125, 216, 343, 512, 729 };

public static boolean isArmstrong(long candidate)
{
    long sum = 0;
    long n = candidate;

    while( n > 0 && sum <= candidate )
    {
        long digit = n % 10;
        n = n / 10;
        sum += cubes[(int)digit];
    }

    return (sum == candidate);
}

Answer 5

Your function both decomposes a number into its digits, and then does the actual calculation on those digits to determine if it's an armstrong number. It would be cleaner to separate out these two concerns into two separate functions

private int[]  getDigits(final long num) { ... }

public isArmstrongNumber(final long num) {
    int[] digits = getDigits(num);
    ...
}