CODEWITHSUNDEEP
javaalgorithm
Alejandro
Alejandro

Reputation: 637

Kattis time limit exceeded for Java factorial

Within a class Main that attempts to find the last digit of a factorial val, why does 

public static void main(String[] args) {
        int testcases = sc.nextInt();

        for (int i = 0; i < testcases; i++) {
            int result = 0;
            int val = sc.nextInt();
            if (val < 3) {
                result = val;
            } else {
                for (int j = 1; j <= val; j--) {
                    result *= j;
                    result %= 10;
                }
            }
            System.out.println(result);
        }

    }

Take so much longer to compute than the same code except for the difference in this snippet:

 for (int j = 1; j <= val; j++) {
     result *= j;
     result %= 10;
 }

I'm aware the second iteration does not provide the right answer, I am curious though as to why it takes so much longer to compute the second as opposed to the first loop.

Upvotes: 1

Views: 479

Answers (1)

Rainbacon
Rainbacon

Reputation: 943

What the loop code is doing

For loops run a block of code multiple times based on 3 conditions:

  1. The starting value of the loop variable (in your case int j = 1)
  2. The condition in which the loop continues (in your case j <= val - So it will stop once j becomes greater than or equal to val
  3. The way that the loop variable changes with each iteration (in your case either j-- or j++

j-- is the decrement operator. It is the same thing as j = j - 1. j++ on the other hand is the increment operator. It is the same thing as j = j + 1

This means that the loop for (int j = 1; j <= val; j--) will run the block of code with j = 1 and then decrement the value of j. It does this as long as j is less than or equal to val. On the other hand, the loop for (int j = 1; j <= val; j++) runs the block of code and then increments the value of j, which it will do as long as j is less than or equal to val.

So, for j-- the sequence of j values that you have is 1,0,-1,-2... while the sequence of values you have for j++ is 1,2,3,4...

An example run

Let's take an example where val is 10. With j++ your loop will run for 1,2,3,4,5,6,7,8,9,10 and then stop, so it runs 10 iterations. With j-- it will run for 1,0,-1,-2,-3.... As you can see, these values are getting further away from 10, which is the value where the loop will stop. What happens is that the loop just keeps running until your integer overflows. When you get to the lowest possible value of an int, the next iteration of decrementing causes the sign of the number to flip and j become the largest possible integer value, which will be greater than 10 and break the loop. In Java, the standard size of an int is 32 bits, so the smallest integer will be -(2^31-1) which is -2,147,483,648. Therefore, if you run with j--, your loop will run over 2 billion times before stopping which is why it takes so much time to run. .

Upvotes: 1

Related Questions