Euler Problem 16

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 21000?

A common first approach to this would be:

  • Compute 21000 with operations on a numeric variable
  • Convert the number into a string
  • Add each digit one by one

However, this won’t work for most langauges because of the restricted sizes in data types. Java’s larger primitives long and double are both 8 bytes, which leaves us with a 264-1 max number assuming that they are unsigned. 21000 is way larger than 264 and it goes without saying that 21000 exceeds the storage space of any Java primitive.

Using a language which allows you to get away with the “common first approach” defeats the purpose of this question!

A great work-around for this problem would be to build the solution to 21000 inside a large array with each digit representing one index.

e.g. instead of long var1 = 100; we would have int[] var1 = {0, 0, 1}; to represent 100. Visually, this looks backwards but array indices are ascending so {0, 0, 1} ==> 100.

My implementation is provided below:

final int DIGIT_SIZE = 500;
// This is the "n" in 2^n
final int EXPONENT_TO = 1000; 

int[] holder = new int[DIGIT_SIZE];

// Set a sentinal for everything, "-1"
for (int i = 0; i < DIGIT_SIZE; i++)
    holder[i] = -1;

// Set the first value to 1
holder[0] = 1;
for (int i = 0; i < EXPONENT_TO; i++) { 
            
    // Double every single digit (building 2^n step by step)
    for (int j = 0; holder[j] != -1; j++)                 
        holder[j] = holder[j] * 2; 
                             
    // If a digit exceeds 9, handle the carry and remainder
    for (int j = 0; holder[j] != -1; j++) {                
        if (holder[j] > 9) {
            holder[j] -= 10;
            if (holder[j + 1] == -1) 
                holder[j + 1] = 1;
            else 
                holder[j + 1] += 1;
        }
    }
}

// Print the sums out
int sum = 0;
for (int i = 0; holder[i] != -1; i++)
    sum += holder[i];

System.out.println(sum);

To conserve memory in cases where our numbers get really big, we can even initialize the array to be of type byte because no value will go over 10. The answer was 1366 if anyone was curious.

Lucas Ou-Yang Hey, thanks for reading! I'm Lucas Ou-Yang, I live in Los Angeles and work fulltime at Snapchat Inc. My main interests are in content ranking and user-experience, I have a good amount of industry experience at both Snapchat and Facebook with ranking & product work. I also authored the most popular python news scraping library on Github: Newspaper, check it out! Feel free to send me an email with any comments, concerns, or requests!

Want to get to know me more? Read my bio and resume.

Share this article with your friends:

comments powered by Disqus
"I saw the angel in the marble and carved until I set him free." - Michelangelo