first and last k digits of number n^n

Question

i have written a c++ code for generating first and last k digits of a number as large as 10^9. (k<=9).

cin>>n>>k;
    cout << (unsigned long)floor(pow(10.0, modf(n*log10((double)n), &dummy) + k - 1)) << " ";  // code that prints the first k digits
    long long int ans = foo(n,k);  // function that prints the last k digits
    if(ans==0)
    {
     for(int i=0;i<k;i++) cout << "0";
    }
    else{
            stringstream ss;
            string s;
            ss<<ans;
            ss>>s;
            if(s.size()!=k)
            {
                 for(int i=0;i<(k-s.size());i++)
          s="0"+s;
            }
            cout<<s;
   }

where function foo() is:

long long int foo(int n, int k)  // code of the function
{
  long long int m=1;
  for(; k > 0; k--) m*=10;

  long long int r=1, t=n % m;
  while(n)
  {
    if (n % 2)
      r = r * t % m;
    t = t * t % m;
    n >>= 1;
  }

   return r;
}

this gives me output as: if given 9 and 3 as inputs, it gives first and last 3 digits of 9 to the power 9 (9^9) i.e. 387 and 489. But I m still missing out some test cases. Can anyone please help me finding out the test case for which my code wouldn't work ?

1 ≤ n ≤ 109, 1 ≤ k ≤ 9 the problem statement: http://www.codechef.com/problems/MARCHA4/

Answer 1

If n^n <= 10^9, in which case your code seems to work fine. However, if you allow bigger n, say 11^11, and ask for the last 4 digits of that, which are 0611, your code will only print 611. Basically, it doesn't print any leading zeroes when it should.

Answer 2

This doesn't really answer the question, and its almost trivially easy, but I figure it might be worth sharing. If there were a "long comment" capability I'd be using it.

EDIT: just noticed using str instead of repr will eliminate the L on its own

def firstAndLastDig(k, num):
    s = str(num)
    return (s[:k], s[-k:])

def firstAndLastDigSelfExp(k,n):
    return firstAndLastDig(k,n**n)

Overflow is not an issue (the only thing is dealing with the L if you use repr instead of str),

firstAndLastDigSelfExp(6,12)
('891610', '448256')

firstAndLastDigSelfExp(42,491)
('209417336844579728122309696211520194012462', '160453713040914743773217804810667483135091')

And neither are leading zeroes

>>> firstAndLastDigSelfExp(4,9)
('3874', '0489')

This isn't do say the modular logs and stuff aren't cool - on the contrary I really liked reading about how you did this without generating the entire number. I didn't know about modf at all until reading OP's question and the body of foo is very interesting.