Calculating the first and last k digits in n^n

Question

I need to print the first k digits and the last k digits in

n^n (n to the power of n, where n is an integer) For example :

Input       Output

n k         First k digits       Last k digits

4 2    -->  25                   56
9 3    -->  387                  489

I sense that it requires some clever mathematics, however I am unable to think of anything as such. Please suggest a way to approach the problem.

This is your homework. You should consider doing the work by yourself. — tamasgal, Sep 08 '12 at 08:31
Also i would question the constraints first. Is n^n big enough not to be computable outright that you have to find another clever way? — fkl, Sep 08 '12 at 08:33
Actually, this is no homework. I was just trying to solve some problems for fun. But I got stuck in it. That's why I asked, and that too just how to approach it. — OneMoreError, Sep 08 '12 at 08:33
n^n would cause an overflow in case of large integer values. — OneMoreError, Sep 08 '12 at 08:34
You tagged your question with "homework". But good try though ;-) — tamasgal, Sep 08 '12 at 08:38
Consider that to some, 'homework' is work you do at home. Nothing more... to most of us it is of course school work. — David Barker, Sep 08 '12 at 09:19
This could have been interesting only if you had asked for the MIDDLE k digits of n^n, for n large enough. — , Sep 08 '12 at 13:04
The question seems to be taken from [here](http://www.codechef.com/problems/MARCHA4) I am not sure if such questions should be (or are being) encouraged. — Shagun Sodhani, Dec 24 '13 at 11:07
@Shagun: Well.. I guess people like me are not so smart.. THey want to learn which may involve asking about how to program and they may use sites like these to ask problems.. Please feel free to ignore us ! — OneMoreError, Dec 24 '13 at 18:47
No offence meant mate. All I mean is such questions should either be on [forums](http://discuss.codechef.com/questions/15398/first-k-digits-of-nn) dedicated to such questions specifically or atleast the context of such problems should be given clearly so that others can learn too. — Shagun Sodhani, Dec 25 '13 at 05:13

score 7 · Accepted Answer · edited May 23 '17 at 12:32

7

The last k digits are easy, you just need to calculate it modulo 10^k. To do this, after every multiplication, just apply the modulo, ie. intermediate_result %= 10^k.

Of course, you will need to calculate 10^k using some other method, because ^ does not mean power of in C or Java.

To find the first k digits, see first n digits of an exponentiation.

edited May 23 '17 at 12:32

Community

1
1

answered Sep 08 '12 at 08:33

ronalchn

12,225
10
51
61

score 2 · Answer 2 · answered Sep 08 '12 at 09:17

Thanks everyone for their help. My final code is

#include <stdio.h>
#include <math.h>

long int lastKdigits(long long n,int k)
{
long long i,res=1,div=pow(10,k);

for(i=1;i<=n;i++)
{
    res=(res*n)%div;
}

return res;
}

long int firstKdigits(long long n,int k)
{
   long double x, y;

   x = n*log10(n);
   y = floor(pow(10,x-floor(x) +k-1));
   return ((int)y);
}

int main()
{

long long n;
int k;

scanf("%lld %d",&n,&k);

printf("%ld\t",firstKdigits(n,k));
printf("%ld\n",lastKdigits(n,k));
}

return 0;

}

score 1 · Answer 3 · answered Sep 08 '12 at 08:34

1

For last k digits it's pretty easy you just need to calculate n^n (mod 10^k) but I don't know any solution for the other k diggits!

answered Sep 08 '12 at 08:34

Lrrr

4,755
5
41
63

Calculating the first and last k digits in n^n

3 Answers3