Algorithm too slow?!

[awkedd]

The program must output the last digit of S=1^4 + 2^4 + 3^4 + … + n^4.
This is my code:

 #include<iostream>
#include<math.h>
using namespace std;
long long n,i,s,k;
int main()
{
    cin>>n;
    s=0;
    for(i=1;i<=n;i++)
    {
        s=s+ pow(i,4);
    }
    k=s%10;
    cout<<k;
    return 0;
} 

When i submit it , i get 40 p out of 100, the reason being "time limit exceeded"
What's the problem ?

[TarikNeaj]

I can see some things improving. For example. Dont use global variables, put the variables inside main.

Also, I dont know why your variables are of type long long. Are you expecting to type in a value of "n" bigger than 2,147,483,647 or even 32,767? "k" is never gonna be anything other than one single digit, so why is that one a long long as well. I think I would have done it this way.

int main()
{
short n, i, k;
	long s; // long or long long depending on how big you want n to be.
	
	std::cin >> n;
	s = 0;
	for (i = 1; i <= n; i++)
	{
		s = s + pow(i, 4);
	}
	k = s % 10;
	std::cout << k;
}

Now I dont know how big of actual improvments these will do but they will do some improvements I would assume, I might have missed something also I dont really have your specific instructions if there were any.

[fg109]

You can't brute force these types of problems, you have to think of shortcuts. Consider trying to find the last digit of 18⁴. Now you can do 18 * 18 * 18 * 18 to find that it equals 104976, and get 6 from that.

But a shorter way is to recognize that the last digit of a product is only dependent on the last digits of its multiplicands. For example, the last digit of 8⁴ is also 6 (8 * 8 * 8 * 8 = 4096). The case is the same for 28⁴, 38⁴, or 9999998⁴.

Also, maybe you shouldn't use the pow function. It's designed to be used with floating point numbers, so maybe its internal workings are more complicated than just multiplying the base number by itself X times.

int getLastDigitOfNumRaised4(int num)
{
    const int digits[] = {0, 1, 6, 1, 6, 5, 6, 1, 6, 1};
    return digits[num % 10];
}

[awkedd]

I found out that the 100p code is

#include <iostream>
using namespace std;
long long s,n,r,i;
int main()
{
cin>>n;
r=n%10;
n=n/10;
s=(33*n)%10;
for(i=1;i<=r;i++)
{
s=(s+i*i*i*i)%10;
}
cout<<s;
return 0;
}

But i don't get this line s=(33*n)%10; , can someone please explain ?

[fg109]

You see my post above? Add up all the digits inside the array and you get 33.

[awkedd]

Oh, you're right.
Thank you !