# 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));
int N = Integer.parseInt(line);

SortedSet<Integer> sort=new TreeSet<>();
for (int i = 0; i < N; i++) {
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++){
if(sort.size()==Integer.parseInt(input[2]))
break;
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?

• Please edit the problem statement. – vnp Aug 1 '14 at 18:59
• I don't quite understand the problem description, can you add example inputs/outputs? – Simon Forsberg Aug 1 '14 at 19:00

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++){
if(sort.size()==Integer.parseInt(input[2]))
break;
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++){
if(sort.size()==input2)
break;
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.

• Adding a variable for input[1] would be good though as you could name it properly. – Simon Forsberg Aug 1 '14 at 19:43
• @SimonAndréForsberg That's the thing though... even after reading rolfl's answer... I still don't know what the code is trying to do. So I wouldn't know what kind of names to use and I wouldn't know what functions to split it up into. Plus, parsing input[1] before it's needed might undo some of the performance gains I made. – Pimgd Aug 1 '14 at 19:45
• @SimonAndréForsberg Oh wait, I made a mistake, because input[1] is in the for loop it CAN be needed multiple times! – Pimgd Aug 1 '14 at 19:51

The TreeSet is a problem because it has a significant time-complexity (and storage size). Adds to the TreeSet are $O(\log{n})$. As the dataset grows, it gets noticeably slower. You can be sure that the test software will do something like: 3 11 5000000 as input, and that will take a long time, and a lot of space, in your TreeSet.

Your solution, because of the TreeSet, essentially becomes one of time complexity $O(n \log{n})$, and space complexity $O(n)$

The solution is much simpler than what you have done... consider a simple function:

private static final int getNthCross(final int a, final int b, final int count) {
int val = Integer.MIN_VALUE;
int nexta = a;
int nextb = b;
for (int i = 0; i < count; i++) {
val = Math.min(nexta, nextb);
nexta = val < nexta ? nexta : (nexta + a);
nextb = val < nextb ? nextb : (nextb + b);
}
return val;
}


This function uses no additional storage, and it simply counts as many times as needed, and uses whichever value comes next.

It runs in $O(n)$, and space complexity $O(1)$