On Mon, Nov 23, 2009 at 6:16 PM, Aditya Shankar <
[email protected]> wrote:
> #include <iostream>
> #include <vector>
> using namespace std;
>
>
> int numdigits(int num) {
> int i = 0;
> while(num > 0) {
> num /= 10;
> i++;
> }
> return i;
> }
>
>
>
> long int getfirstk(int num, int k, int digits) {
> char* c = (char*)malloc(sizeof(char) * digits);
> sprintf(c,"%d",num);
> c[k] = '\0';
> int ret_val = atoi(c);
> free(c);
> return ret_val;
> }
>
>
> pair<long int,long int> getFirstAndLast(int num, int k) {
> int firstk = 0;
> int num_dig = numdigits(num);
> int front_digits_to_keep = k+2;
> int last_digits_to_keep = k;
> int last_mask = 1;
> for(int i = 0; i < last_digits_to_keep; i++ ) {
> last_mask *= 10;
> }
> long int lastk = 1;
> long int firstk_plus2 = 1;
> int n = num;
> while(n > 0) {
>
> lastk = (lastk * num)% last_mask;
> firstk_plus2 = getfirstk(firstk_plus2 * num, front_digits_to_keep,
> front_digits_to_keep);
>
Basically the only take-away here is that the 1st k+2 digits are all you
need, the other digits cannot affect the 1st k digits. (assuming that n is
2 digit, otherwise it will overflow anyway.)
> n--;
> }
> firstk = getfirstk(firstk_plus2, k, front_digits_to_keep);
> return pair<long int,long int>(firstk, lastk);
> }
>
>
> int main(int argc, char* argv[]) {
>
> int i = 19;
>
> if(argc == 3) {
> pair<int,int> p = getFirstAndLast(atoi(argv[1]),atoi(argv[2]));
> cout << p.first << " " << p.second << endl;
> }
>
>
> }
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=.
