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);

• gardenhead: digitSum should be initialized to 0, and remainder should be declared when it is assigned to, which is inside the loop.
• Dair: @gardenhead: Technically it's guaranteed to be zero. But they also say "Relying on such default values, however, is generally considered bad programming style." (docs.oracle.com/javase/tutorial/java/nutsandbolts/…). So thanks. I changed it.
• gardenhead: Clarity over brevity :)
• janos: Another reason to declare a variable inside a loop is to limit its scope to that loop. It's good to limit the scope of variables to the smallest possible scope to prevent accidental misuses

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;
 }
}

• Jae Bradley: > Why is there an interface and a BlahBlahImpl? This is how I was taught to write Java - basically the logic, as explained to me, was that the one-to-one-ness of interfaces to implementations makes testing and dependency injection easier. I know there are solutions like Guice, but this pattern feels much more explicit.
• Jae Bradley: Why isn't the solution just a static function? You're right, it probably should be Why does the parameter need to be final? I don't think that the parameter needs to be final, but what is the downside to specifying final? I don't see any downside, but I see plenty of upside to specifying any variable that you choose to not mutate as final, such as not mistakingly mutating a variable inappropriately in a later context.
• 200_success: A static function is still perfectly testable. And final is not that useful for primitive parameters (which are always immutable anyway as far as the outside world is concerned). Also note that final on an array won't prevent modification of its contents, and final on an object won't guarantee that it is mutation-free. Therefore, I consider final on parameters to be noise. (On the other hand, final fields can be helpful.)
• Jae Bradley: I was mostly thinking from the context of "if I gave this code to somebody else to maintain" or "received code from somebody to maintain" - I think being explicit about final could at the very least, prevent object reference changes (though, as you point out, makes no mutability guarantees) and reassignment of primitive parameters. Now you could make the argument that anybody worth their salt should consider every single code change they make and what the consequences are and that the cases I've pointed out are trivial - but I think that can be a relatively dangerous assumption.
• 200_success: General opinion of usage of final for parameters

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 \2ドルm\$ 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);
 ...
}