15,880,392 members
See more:
449 multiplied by 449, repeated 524 times, what number are the last four digits of the result ,may I ask how to use the code to achieve it?

449^524,What are the last four number of the result?
Posted
Rob Philpott 3-Nov-11 7:02am
Project Euler?
PEIYANGXINQU 3-Nov-11 8:09am
No,it just an interview question,it ask me to make codes to solve it
Amir Mahfoozi 4-Nov-11 1:07am
Thanks for sharing it with us ;)

## Solution 1

Use BigInteger[^]

`BigInteger answer = BigInteger.Pow(449, 524);`

edit: just for fun
```   (449`*524):ToLongString
5,985,255,380,621,525,587,490,777,673,858,621,562,635,659,084,907,797,237,320,028,111,013,543,061,232,489,766,893,321,851,890,503,459,137,446,484,633,586,146,695,619,957,515,587,290,585,198,033,254,001,638,806,546,089,460,292,737,095,343,178,522,652,616,695,479,855,321,550,996,925,652,471,605,562,928,046,290,972,703,902,296,140,220,076,897,750,949,934,904,375,038,506,055,615,873,384,539,662,912,152,178,307,914,016,469,809,780,515,684,903,688,070,053,848,279,441,777,629,182,553,799,249,510,801,216,060,287,684,586,308,336,701,599,742,446,329,413,880,660,380,827,531,021,671,119,107,622,792,649,810,670,450,188,392,552,151,977,124,101,612,531,168,697,678,029,514,483,886,645,408,109,516,123,799,296,356,713,818,018,208,226,789,861,824,603,641,985,253,774,155,777,930,965,362,607,457,844,494,860,140,173,216,937,713,140,137,600,632,768,457,610,720,933,836,147,660,285,216,580,460,832,807,212,804,681,782,763,816,442,705,820,781,897,969,714,373,145,998,945,626,299,659,324,249,139,716,383,245,273,614,165,802,707,184,902,083,128,759,575,258,978,390,815,404,465,839,840,654,586,280,060,428,999,298,859,926,797,944,027,388,946,915,862,715,360,444,142,882,852,212,548,775,203,760,260,073,303,449,804,948,058,590,825,825,758,946,769,524,742,006,380,434,838,779,543,344,435,420,987,795,645,900,233,998,333,104,279,045,252,997,541,059,735,359,625,564,855,740,685,616,367,833,186,985,578,207,521,896,280,913,934,556,084,302,333,480,725,938,153,972,689,612,074,532,168,301,776,882,216,798,672,206,185,183,395,822,325,978,564,884,091,292,018,411,398,669,092,647,107,800,852,498,315,458,722,629,042,712,089,321,763,768,280,751,483,199,255,891,172,438,174,916,083,055,594,263,264,732,844,962,353,547,298,264,651,846,308,048,770,159,600,464,359,526,742,877,478,241,864,026,155,585,905,254,225,180,498,197,204,222,756,828,036,682,898,517,556,775,411,630,941,779,201```

v2
UJimbo 3-Nov-11 7:15am
Show him how to get the substring containing the last 4 numbers and you get my 5 marks Bob :)
BobJanova 3-Nov-11 7:52am
I thought giving a complete answer to what's probably a homework or trivia question was a bit much :P. If he can't work out how to do that then he doesn't deserve the answer.
PEIYANGXINQU 3-Nov-11 8:40am
Thank you!
Roger Allen 3-Nov-11 13:26pm
Wouldn't this get the last 3 digits and the ',' character?
Which means it would not fulfill the request of the last 4 digits...
BobJanova 3-Nov-11 13:48pm
I don't think BigInteger's string output has punctuation in it. The output in my solution is from some code I have to do extended precision (I didn't have a BigInteger test project lying around).

## Solution 4

I think the underlying question is how to get the result without using an extended precision library.

```   449 * 449 = 201601
201601 * 449 = 90518849

but we can see only the four least significant digits are required as
1601 * 449 = 718849```

Coding a suitable loop gives the result in a speedy 8 microseconds!

[EDIT]
In response to the comment
The general technique is demonstrated with a small calculation and there is no need to go beyond 449^3 (90518849) as the result is applicable to any power.

The important point is that in each iteration of the calculation we need to carry forward only the last 4 digits of the previous result.

C#
```Int32 result = 1;
for (Int32 i = 0; i < 524; ++i) {
result = (result * 449) % 10000;
}```

Alan.

v3
PEIYANGXINQU 3-Nov-11 14:35pm
En，Thank you very much.You way is better than the direct calculation.

## Solution 7

What a boring question:
C++
```int m = 449;
int r,i;
for(r=m,i=1;i<524;i++) r = (m*r)%1000;
// three digits: 201
for(r=m,i=1;i<524;i++) r = (m*r)%10000;
// four digits: 9201
for(r=m,i=1;i<524;i++) r = (m*r)%100000;
// five digits: 79201
for(r=m,i=1;i<524;i++) r = (m*r)%1000000;
// six digits: 779201```

Regards.

Amir Mahfoozi 4-Nov-11 1:03am
+5 We have a genius here ;)
mbue 4-Nov-11 7:13am
Thanks for the candy ;)

## Solution 2

Hint: only the last four digits of the result are required.

PEIYANGXINQU 3-Nov-11 9:46am
Thank you.May be we do not have to calculate the result.

## Solution 6

It doesn't get any easier than this.
C++
`ReallyBigNumber % 10000`