CSES Number Spiral Java TLE

Question

I am trying to solve the CSES Number spiral problem https://cses.fi/problemset/task/1071/ However, I get the TLE problem. How can make my code more efficient?

import java.io.*;

public class cses7 {
    static long valPerm = 1;
    static long powresult = 1;
    
    public static void main(String[] args) throws IOException{
        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        int numCoord = Integer.parseInt(bufferedReader.readLine());
        long x;
        long y;
        while (numCoord > 0) {
            String[] input = bufferedReader.readLine().split(" ");
            y = Long.parseLong(input[0]);
            x = Long.parseLong(input[1]);
            numCoord--;
            if (y == x) {
                System.out.println(1 + x*(x-1));
            }
            if (y > x) {
                mathpower(-1, y);
                valPerm = (long) (1 + y*(y-1) + powresult *(y-x));
                System.out.println(valPerm);
            } else {
                mathpower(-1,x);
                valPerm = (long) (1 + x*(x-1) + powresult *(y-x));
                System.out.println(valPerm);
            }
        }

    }
    private static void mathpower(long n, long m) {
    
        while (m != 0) {
          powresult *= n;
          --m;
        }
    }

}
```

Answer 1

[As suggested by Toby Speight, I hope you add a summary of the problem to the question, as Internet links tend to have a shorter lifespan than stackexchange questions.]

I'll first cover performance-specific topics, that might account for the "Time Limit Exceeded" failure, and then comment on code style (as this is Code Review, you always get more than you specifically asked for).

(And before changing your program according to the comments here, I'd ask you to do the correctness check that you'll find at the end of my text.)

Performance

mathpower()

You are implementing the mathematical power operation in the most straightforward (and thus slowest) possible way: by doing many multiplications. As x and y can be numbers up to a billion, a single mathpower() call can take a billion multiplication steps. As up to 100000 tests can be requested, your program will do up to 100 trillion multiplications - this will not finish within one second, expect it to consume at least a day or so. Computers are fast today, they can do around a billion multiplications per second, but not the trillions that you'd need.

But you can do better. You only raise -1 to some power, meaning that the result is always either +1 or -1, with +1 for even exponents, and -1 for odd exponents. So, instead of the looped multiplications, check for even/odd exponents.

Style

mathpower()

The biggest style flaw I see is as well in the mathpower() method. A method that computes some number should return the computed value as its return value. Your method is declared void and stores its result in some static field powresult, making it hard for a reader to understand that in

            mathpower(-1, y);
            valPerm = (long) (1 + y*(y-1) + powresult *(y-x));

the powresult field has something to do with the mathpower() call. Wouldn't it be much more natural to see

            long powresult = mathpower(-1, y);
            valPerm = (long) (1 + y*(y-1) + powresult *(y-x));

or even

            valPerm = (long) (1 + y*(y-1) + mathpower(-1, y) * (y-x));

And having the result as the return value makes your method much more flexible. You can have multiple calls and store their results into multiple variables or fields, which is impossible with your code style.

numCoord loop

The

    while (numCoord > 0) {
        // ...
        numCoord--;
        // ...
    }

is hard to read. Let my explain my analyzing steps when seeing such a loop:

• There's a loop while numCoord is greater than zero.
• What is numCoord? It's the number of coordinate pairs (tests) to be executed.
• But how does the number of coordinates change? That comes from the input. Weird.
• Let's check. Oh, somewhere in the middle of the loop body is a numCoord--; statement that changes the value.
• This numCoord--; statement is not inside any conditional statement, so it's executed exactly once per iteration.
• Okay, then it's a simple backward-counting loop, re-using the input variable as the counter.

The idiomatic loop for such a simple counter would read:

for (int i=0; i<numCoord; i++) {
    // ...
}

Any Java (or C / C++ / C# and so on) developer will immediately understand this as the everyday simple counting loop repeating numCoord times.

Wildcard import

You wrote

import java.io.*;

This opens a kind of "surprise package". You get everything from java.io, no matter if you need it or not.

If you want to produce reliable code that will also work with future Java versions (where there might be more classes in the surprise package), maybe in 5 or 10 years, it's better to replace this wildcard import with the explicit ones that you really need:

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

(That's a rule coming from 20+ years of working with Java, seeing its class library evolve from quite big in the 1.1 beginnings to overwhelmingly huge with current versions.)

Fields vs. variables

You use a field

static long valPerm = 1;

just for storing a value for a very short time, as in:

            valPerm = (long) (1 + y*(y-1) + powresult *(y-x));
            System.out.println(valPerm);

I'd write it as:

            long result = (long) (1 + y*(y-1) + powresult *(y-x));
            System.out.println(result);

(or even System.out.println((long) (1 + y*(y-1) + powresult *(y-x))); )

The guideline is not to have a variable or field hanging around for longer than necessary. A field exists "permanently", so it should only be used for information that is needed all over the lifetime of the class. For storing a value from one statement to the very next one, a local variable is the correct choice.

Naming

Giving intellegible names to classes, methods, fields and variables is very important for production-quality code, making it easy (or hard) for your fellow developers to understand your program, and also for you if you once return to some program you wrote e.g. a year ago.

You generally did a good job with method and variable names. Only valPerm is an exception, as I'd only understand that it's some permanent value. But that doesn't match its usage (as I said, only used for very short-term storage), and doesn't tell me what's inside: the task result, being the content of the cell addressed with x and y. So, my naming would be something like taskResult or cellContent.

Package

Typically, you should place code into a package name that you "own" (e.g. com.stackexchange.codereview.jota), to make collisions with other developers highly unlikely. But with sites like CSES, you often have to follow their naming, so for the given task, using the unnamed package probably can't be avoided.

Correctness

Have you tested your program? Creating a useful set of test data can be quite challenging, and the short example input given at CSES surely does not cover all relevant situations. Especially, every solution has its own logic, and thus can have its own special cases where it might fail.

One risk that I see is that the mathpower() method starts with whatever is found in the powresult field, which might be either 1 or -1, depending on the situation of the previous test case. Most probably, you are expecting it to start from powresult = 1. The initialization you do in the declaration static long powresult = 1; is only effective for the very program start, not helping you between the test case iterations.

Seeing this risk, you should find a test case that leaves powresult as -1 (having an odd (y-x) value), and using this x/y pair twice in the input. I guess that the second result will differ from the first one.

This risk will go away if you stop using the static fields and instead use return values and local variables.