CODEWITHSUNDEEP
c#math
Mr. Mr.
Mr. Mr.

Reputation: 4285

How does this C# code work out the answer?

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.

Upvotes: 2

Views: 239

Answers (5)

Jaime Torres
Jaime Torres

Reputation: 10515

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.

Upvotes: 6

mjgpy3
mjgpy3

Reputation: 8957

  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.

Upvotes: 1

pizen
pizen

Reputation: 474

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

Upvotes: 4

Charleh
Charleh

Reputation: 14002

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)

Upvotes: 1

CodesInChaos
CodesInChaos

Reputation: 108880

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.

Upvotes: 2

Related Questions