_Muhammad's blog

Getting TLE in 112. a^b-b^a
By _Muhammad, history, 7 years ago, In English

My code getting TLE in sgu 112 problem. I am new to java programming so I am not understanding why my code is getting TLE. I also have submitted 3 code from github for this problem. They also got TLE. Now what should I do? Question link : http://mirror.codeforces.com/problemsets/acmsguru/problem/99999/112

My code :

//In the name of ALLAH

//package OverRiding;

import java.math.BigInteger;
import java.util.Scanner;

public class Example1 {

    public static void main(String[]args) {


        Scanner cin = new Scanner( System.in );

        BigInteger bigA = cin.nextBigInteger();
        BigInteger bigB = cin.nextBigInteger();
        BigInteger aPowb, bPowa;
        aPowb = bigA.pow ( bigB.intValue() );
        bPowa = bigB.pow ( bigA.intValue() );

        BigInteger ans = aPowb.subtract ( bPowa );
        System.out.println(ans);


    }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The Problem is in Scanner, I think. Try use another input class

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro! please tell me about that input class which you have used to solve it. Name or tutorial link.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If your Logic is different then tell me the logic.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I use bufferedReader and stringtokenizer Don't know if there are some faster way.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

I used C to solve this problem. With <math.h> using pow function I get wrong answers on test 1. Then I used a different method and tried without using the pow function and now I'm getting wrong answers on test 5. My code seems fine. I've checked my code over and over again but It doesn't work. Here's my code if anyone can answer me where I did wrong it would be a big help.

include<stdio.h>

int main()

{

long long int a, b;
long long int r1 = 1, r2 = 1;

scanf("%lld  %lld",&a,&b);

long long int c = a;
long long int d = b;

while(b!=0)
{
    r1 = r1 * a;
    b--;
}
while(c!=0)
{
    r2 = r2 * d;
    c--;
}

printf("%lld\n",(r1-r2));

return 0;

}

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hmmm $$$100^{100}$$$ definitely cannot be represented as a 64-bit integer (long long int). Try implementing big integers by hand or use some implementations that are already published online.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh, that's it then. I have understood the problem now. Thank you very much.

      I'm a beginner so I don't really know much about big integers, bigger than long long int. I've searched for some info and found GMP library and some said to use array.

      For this problem array isn't a good choice I guess. I don't know how to use GMP and couldn't find any useful easy to understand tutorial for that.

      Can you give me a direction where to look, or how the implementations of big integers works in C?

      Thank you for your time. Hope you and your family are doing okay in this pandemic.

      God bless us all.

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A and b are big number it can be 100^100 — 100^100 so the long long can't store this huge value you want to store it in a string and subtract it their is a good article in geeksforgeeks

    https://www.geeksforgeeks.org/difference-of-two-large-numbers/

    → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I am not java expert but I think there should be something like cin.close() at the end, or System.exit(0), or System.out.flush(). The calculation does not need much time.

→ Reply