2

I have solved the project Euler problem 16 but discovered this rather novel approach but I cannot get my head around the technique employed (from http://www.mathblog.dk/project-euler-16/):

int result = 0;

BigInteger number = BigInteger.Pow(2, 1000);

while (number > 0) {
    result += (int) (number % 10);
    number /= 10;
}

My version seems more conventional but I think the above approach is cooler.

var result = BigInteger
    .Pow(2, 1000)
    .ToString()
    .Aggregate(0, (total, next) => total + (int) Char.GetNumericValue(next));

How does the mathematics work on the first approach, it is cool, but I need some explanation to help me understand, so if someone would be so kind to explain to me I would really appreciate it.

NOTE: If I have posted in the wrong section please let me know the better place to ask.

2
  • 3
    It took me longer to understand your technique than it took me to understand the other code. What seems obvious or conventional depends a lot on what you're used to. Aug 15, 2012 at 15:14
  • 1
    Why not .ToString().Select(char.GetNumericValue).Aggregate() ? Gets rid of the messy lambda.
    – Ben Voigt
    Jan 22, 2015 at 18:00

5 Answers 5

6

value % 10 will return the last digit (remainder after dividing by 10). Dividing the integer by 10 will remove this number.

Think of the number as a list, and you're just dequeuing the list and summing the values.

4
  • 2
    I think the key thing to mention here is the integer division technique truncates instead of yielding the fractional value. Aug 15, 2012 at 15:13
  • Had to read what you said a few times to get it, it is rather simple when you think about it in the 'right' way, thank you.
    – Mr. Mr.
    Aug 15, 2012 at 15:20
  • 2
    Awarding yours as the answer due to highest up votes and as first person to answer.
    – Mr. Mr.
    Aug 15, 2012 at 15:21
  • It's good to be first :). Cleaned up answer to say "List" instead of "Stack" for the purists. Aug 15, 2012 at 15:24
4

The modulus operator provides the remainder from the division. So, mod 10 is going to be the one's place in the number. The integer division by 10 will then shift everything so it can be repeated.

Example for the number 12345:

12345 % 10 = 5
12345 / 10 = 1234
 1234 % 10 = 4
 1234 / 10 = 123
  123 % 10 = 3
  123 / 10 = 12
   12 % 10 = 2
   12 / 10 = 1
    1 % 10 = 1
    1 / 10 = 0 (loop ends)

The addition is performed on the result of each modulus so you'd get 5+4+3+2+1

1
  • 1
    +1 for writing it down so someone can understand what you are talking about, unlike my answer :D
    – Charleh
    Aug 15, 2012 at 15:42
2

number % 10 extracts the least significant decimal digit. e.g. 12345 => 5

number / 10 removes the least significant decimal digit. This works because integer division in C# throws away the remainder. e.g. 12345 => 1234

Thus the above code extracts each digit, adds it to the sum, and then removes it. It repeats the process until all digits have been removed, and the number is 0.

1

It's quite simple:

Imagine this:

number = 54

It uses modulo to get the remainder of this divded by 10

e.g. 54 / 10 = 5 remainder 4

It then adds this digit (4) to the result, then divides the number by 10 (storing into int which discards decimal places)

so then number = 5

same again, 5 / 10 = 0 remainder 5

Adds them togther, result is now 9

and so on until the number is 0 :)

(in this case 9 is the answer)

1
  1. They found the number 2^1000.

  2. Modulo 10 gets the least significant digit. E.G. 12034 % 10 = 4

  3. Dividing by 10 strips the least significant digit. E.G. 12034 / 10 = 1203

  4. They sum up these least significant digits.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.