CODEWITHSUNDEEP
c++algorithm
Vaibhav
Vaibhav

Reputation: 6998

first and last k digits of number n^n

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/

Upvotes: 5

Views: 2888

Answers (5)

Ben Voigt
Ben Voigt

Reputation: 283624

I think the problem is using floating point. Finding the first digit of a number actually requires perfect precision.

Unfortunately, the contest judge evidently doesn't understand that "number of significant digits" != "number of correct digits".

Perhaps there is some clever way to exactly compute (n*n, n = 10*9) without exhausting memory, but finding the first digits of a very good estimate is simply not the same as finding the first digits of the answer.

Upvotes: 0

jon_darkstar
jon_darkstar

Reputation: 16768

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.

Upvotes: 1

Ben Voigt
Ben Voigt

Reputation: 283624

Are you told that n is a positive integer? For example, (-8)^(-8) is perfectly well expressible in decimal but your program can't handle it.

Upvotes: -1

Ben Voigt
Ben Voigt

Reputation: 283624

Assume that k = 9. Now, m = 1e9, and t <= 1e9 - 1. t * t then may be as high as 1e18 - 2e9 + 1, which needs ... 59.8 bits.

Ok, not a problem with a 64-bit long long int, which has 63 bits of magnitude (and 1 of sign), but I'll leave this here so others don't repeat the same analysis.

Upvotes: -1

IVlad
IVlad

Reputation: 43477

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.

Upvotes: 2

Related Questions