Calculating the Nth number in the supertable of two numbers

Below is the problem:


Little Timmy is exceptionally good at math tables, so his teacher decided to make things a bit more interesting. His teacher gave him two numbers, A and B, and told him to merge the tables of A and B in order (ascending order), removing the duplicates and thus supertable of A and B, and asks Little Timmy the Nth number. Given A, B and N, calculate the Nth number in the supertable of A and B.

Input


First line contains number of test cases T . Each test case contains three integers A, B and N.

Output


For each test case print the Nth number of the supertable.

Here is my code:

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine();
    int N = Integer.parseInt(line);

    SortedSet sort=new TreeSet<>();
    for (int i = 0; i < N; i++) {
        String[] input=br.readLine().split(" ");
        if(input[0].equals(input[1])){
            System.out.println(Integer.parseInt(input[0])*Integer.parseInt(input[2]));
        }else{
        for(int i1=1;i1<Integer.parseInt(input[2]);i1++){
            sort.add(Integer.parseInt(input[0])*i1);
            if(sort.size()==Integer.parseInt(input[2]))
                break;
            sort.add(Integer.parseInt(input[1])*i1);
            if(sort.size()==Integer.parseInt(input[2]))
                break;
        }
        System.out.println(sort.toArray()[Integer.parseInt(input[2])-1]);
        }
    }

The problem is that my code is taking too long to run and I am not passing my test cases because of time constraints. How can I optimize this code so that it may run fast?

If I just look at the code, without looking at the algorithm, here's something you could optimize:

String[] input=br.readLine().split(" ");
if(input[0].equals(input[1])){
    System.out.println(Integer.parseInt(input[0])*Integer.parseInt(input[2]));
}else{
    for(int i1=1;i1<Integer.parseInt(input[2]);i1++){
        sort.add(Integer.parseInt(input[0])*i1);
        if(sort.size()==Integer.parseInt(input[2]))
            break;
        sort.add(Integer.parseInt(input[1])*i1);
        if(sort.size()==Integer.parseInt(input[2]))
            break;
    }
    System.out.println(sort.toArray()[Integer.parseInt(input[2])-1]);
}

What's up with all the parseInt? I have a feeling parseInt is very expensive.
So let's do that only once.

No matter what you do, you always need input[2] and input[0].
You only need input[1] once you reach the for loop, so I've moved the declaration near the for loop.

String[] input=br.readLine().split(" ");
int input0 = Integer.parseInt(input[0]);
int input2 = Integer.parseInt(input[2]);
if(input[0].equals(input[1])){
    System.out.println(input0*input2);
}else{
    int input1 = Integer.parseInt(input[1]);
    for(int i1=1;i1<input2;i1++){
        sort.add(input0*i1);
        if(sort.size()==input2)
            break;
        sort.add(input1*i1);
        if(sort.size()==input2)
            break;
    }
    System.out.println(sort.toArray()[input2-1]);
}

There's probably a greater optimization to be made on a algorithmic level, but this at least fixes one issue.

StackExchange Code Review Q#58785, answer score: 3