Forum

Post 19.05.2009   # 1
Subject CodeFu 2009 Round 2 - Problem 500
500. Sum Of Powers

The last digit of a power of a number depends only on the last digit of the number. Even more, the last digit is periodically repeated after some power index.

For example, lets see what are the powers of two: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 ...

Or, the last digit of this powers: 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6 ... We can see that the sequence 2, 4, 6, 8 is repeated all over again.

For every other digit there is a similar sequence of length 1, 2 or 4.

This the table for all the digits:

last digit of:  N    N^1   N^2   N^3   N^4   N^5   ...    repeats after  
-----------------------------------------------------------------------
0 0 0 .. .. .. ... 1
1 1 1 .. .. .. ... 1
2 2 4 8 6 2 ... 4
3 3 9 7 1 3 ... 4
4 4 6 4 .. .. ... 2
5 5 5 .. .. .. ... 1
6 6 6 .. .. .. ... 1
7 7 9 3 1 7 ... 4
8 8 4 2 6 8 ... 4
9 9 1 9 .. .. ... 2

Having this in mind, we can solve the problem by finding the last digit of all the powers, and than doing a sum over this last digits. Here is the complet solution:

public class SumOfPowers {

int[] repeat = new int[] {1, 1, 4, 4, 2, 1, 1, 4, 4, 2};
int[][] last = new int[][] {
{0, 0},
{1, 1},
{6, 2, 4, 8, 6},
{1, 3, 9, 7, 1},
{6, 4, 6},
{5, 5},
{6, 6},
{1, 7, 9, 3, 1},
{6, 8, 4, 2, 6},
{1, 9, 1}
};

public int lastDigit(int N) {
int sum = 0;
for (int i = 1; i <= N; ++i) {
int a = i % 10;
int pow = (i+1) % repeat[a];
sum += last[a][pow];
sum %= 10;
}
return sum;
}
}


bilievsk is offline Reply

Please login to post reply.