Imagine you’re in a spaceship being hunted down by co-workers who’ve been taken over by an evil force. The only way to open the lock to the safe area of the ship is by finding a set of happy primes. This is exactly what happened to the main character in the sci-fi TV series Dr. Who.

We all know what a prime number is, and there are numerous algorithms to determine whether a number is a prime, but what is a happy number? Well, the term “happy number” comes from the world of recreational mathematics and it even has its own Wikipedia page. The definition is actually very simple:

• Start with a number N
• Take all the digits from N, square them and add them together
• Then repeat the operation on the result

If repeated execution of this operation ends in the number 1, the number N is called a happy number. If it results in an endless loop, the number N is called an unhappy, or sad number.

Wrong for two reasons

At a job interview, you might get a question like: “Write an algorithm to determine whether a number is a happy number. It should return true if it’s happy, false if it’s unhappy”. Let’s try to solve this problem.

Getting the digits from a number seems easy, and you might be tempted to write it like this:

char buffer[3];
sprintf (buffer, “%d”, number); 
size_t sum = buffer[0]*buffer[0] + buffer[1]*buffer[1];

This code is deceptively simple but it’s wrong for two reasons:

• It incorrectly assumes that the numeric value of a character is equal to the numeric value of the digit. It’s not. The character ‘0’ has ASCII value 0x30, which clearly isn’t zero;
• It assumes that the number consists of only 2 digits. Even when the original question would have been ‘start with a number between 10 and 99’, there is no guarantee that all intermediate values remain smaller than 100.

Look mom

So, lesson #1 would be: when dealing with numeric information, you should use numeric algorithms. Getting the digits from a number is actually very easy: just use modulo-10 to get one digit, perform an integer divide-by-10, and repeat. While looping, take the square of the digits, like this:

auto sum = size_t{0};
while (number)
{
  auto remainder = number%10;
  sum += remainder * remainder;
  number /= 10;
}

Look mom, no sprintf function needed.

Check using a vector

The next step is to repeat this operation until we reach 1. Let’s wrap the calculation above in a function called calculate and write the final algorithm:

auto isHappy(int number)
{
  while (number!=1)
    number = calculate(number);
  return true;
}

Wait, and exactly when do we return false? What happens if the number is not a happy number? Right, the function will never terminate. What’s missing is a check on whether we already encountered the number before.

The most obvious way to check this is to keep all values in a simple std::vector.  In every iteration, check whether the value is already in the vector, and if it isn’t, add it to the vector and continue.

Extending the question

The interviewer might ask you for alternative ways to check for recurring numbers.  Would an std::set be more efficient? Should we use an std::bitset to check whether we already encountered a number? What would be the fastest possible implementation?

Try to extend the original question to show the interviewer that you are really thinking outside the box, not bound by what you learned from textbooks. For example, propose to write an algorithm that returns all happy numbers between 1 and 1 million. It could be a good opportunity to show your knowledge of multi-threading too.

No spaceships, still a lot of fun

Okay, that was fun, but will we ever need to solve this kind of problem in real life? Probably not. But lots of other problems will come your way and solving them is important when you work in an innovative software company like OMP. We don’t build spaceships and our co-workers haven’t been taken over by an evil force, but OMP is always looking for people with a spark of creativity. Thinking outside the box is key to solving real-life problems. So, what’s keeping you?