Happy Number Counter

Question

Task

Write an implementation that determines the count of happy numbers between a given start and end value.

Implementation

public class HappyNumberCounter {

  public static int getLastDigit(final long number) {
    return Math.toIntExact(number % 10);
  }

  public static long digitSquareSumCalculator(final long number) {
    int remainder = getLastDigit(number);
    long quotient = number / 10;
    long digitSum = remainder * remainder;
    while (quotient > 0) {
      remainder = getLastDigit(quotient);
      quotient = quotient / 10;
      digitSum = remainder * remainder;
    }

    return digitSum;
  }

  public static long countHappyNumbersInRange(final long startInclusive, final long endInclusive) {
    final Map<Long, Boolean> happyNumbers = new HashMap<>();
    long count = 0;
    for (long index = startInclusive; index <= endInclusive; index++) {
      long number = index;

      // case 1: already been cached
      // case 2: has not been cached
      // case 3: has not been cached but starts with 1 or 4
      // case 4: has not been cached and does not start with 1 or 4

      Boolean isHappy = happyNumbers.get(number);
      if (isHappy == Boolean.TRUE) {
        count++;
      } else if (isHappy == null) {
        long lastDigit = getLastDigit(number);
        if (lastDigit == 1) {
          happyNumbers.put(number, Boolean.TRUE);
          count++;
        } else if (lastDigit == 4) {
          happyNumbers.put(number, Boolean.FALSE);
        } else {
          final List<Long> numbers = new ArrayList<>();
          while (lastDigit != 1 && lastDigit != 4 && isHappy == null) {
            numbers.add(number);
            number = digitSquareSumCalculator(number);
            isHappy = happyNumbers.get(number);
            lastDigit = getLastDigit(number);
          }

          for (final Long num : numbers) {
            happyNumbers.put(num, isHappy);
          }

          if (isHappy) {
            count++;
          }
        }
      }
    }
    return count;
  }

}

Feedback

• I feel like my implementation is too long (i.e. there's too much logic happening in one method), but I can't seem to find any natural break points.

Answer 1

First of all, your code doesn't work properly: there are 143 happy numbers between 1 and 1000 but your code (after fixing a NullPointerException) will count 614. The logic is indeed too complicated and you can simplify this a lot.

---

First of all, let's consider the method that calculates the sum of squares of each digits. Instead of digitSquareSumCalculator, a more descriptive name would simply be sumOfSquaredDigits.

public static int getLastDigit(final long number) {
    return Math.toIntExact(number % 10);
}

Why use Math.toIntExact? No overflow can happen here since we're taking the modulo 10 so the result is between 0 and 9. If you're using just to cast the result to an int, it would be clearer to just cast.

public static long digitSquareSumCalculator(final long number) {
    int remainder = getLastDigit(number);
    long quotient = number / 10;
    long digitSum = remainder * remainder;
    while (quotient > 0) {
        remainder = getLastDigit(quotient);
        quotient = quotient / 10;
        digitSum = remainder * remainder;
   }
   return digitSum;
}

This contains duplicated logic: you can see that the first part of the method is the same as what goes in the while loop. You can fix that by not using a temporary variable quotient but reusing the variable number (and thereby dropping the final). The number given to the method won't be changed.

public static long sumOfSquaredDigits(long number) {
    long digitSum = 0;
    while (number > 0) {
        int remainder = (int) (number % 10);
        number /= 10;
        digitSum += remainder * remainder;
    }
    return digitSum;
}

This code shows that actually, you don't need the getLastDigit method.

---

The main part of the code is indeed clunky. You're missing an obvious method here: you want to determine if a number is happy or not, therefore it would make sense to have a method isHappy(number) that determines if the given number is happy or not.

The code of this method must do the following:

• Calculates the sum of squared digits of the number
• If the number obtained has already been obtained, return false; else continue. If we hit 1, return true.

We can store the visited numbers in a Set (to have constant-time look-up):

public static boolean isHappy(long number) {
    Set<Long> numbers = new HashSet<>();
    while (number > 1 && !numbers.contains(number)) {
        numbers.add(number);
        number = sumOfSquaredDigits(number);
    }
    return number == 1;
}

With such a method, you can then have a very simple for loop:

public static long countHappyNumbersInRange(final long startInclusive, final long endInclusive) {
    long count = 0;
    for (long index = startInclusive; index <= endInclusive; index++) {
        if (isHappy(index)) {
            count++;
        }
    }
    return count;
}

---

Now, we can make a simple but big improvement in terms of performance (just like you were trying to in your code). When we are determining if a given number is happy or not, we're also determining whether all the visited numbers are happy or not. So we don't need to check every number between the bounds and we can store a cache of happy or not happy numbers. So let's introduce a cache

private static final Map<Long, Boolean> CACHE = new HashMap<>();

that, for a given number, will hold whether it is a happy number of not. Then, when the method isHappy is running, we can stop early if we encounter a number we've already seen before. If that's the case, then we put in the map all the numbers encountered with the happyness of the starting number.

public static boolean isHappy(long number) {
    if (CACHE.containsKey(number)) {
        return CACHE.get(number);
    }
    Set<Long> numbers = new HashSet<>();
    while (number > 1 && !numbers.contains(number)) {
        numbers.add(number);
        number = sumOfSquaredDigits(number);
        if (CACHE.containsKey(number)) {
            boolean result = CACHE.get(number);
            for (long n : numbers) {
                CACHE.put(n, result);
            }
            return result;
        }
    }
    boolean result = number == 1;
    for (long n : numbers) {
        CACHE.put(n, result);
    }
    return result;
}

---

I ran this code to determine all the happy numbers between 1 and 1 million and it gave the result instantly.