1
\$\begingroup\$

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<Integer> 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?

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

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.

\$\endgroup\$
  • \$\begingroup\$ Adding a variable for input[1] would be good though as you could name it properly. \$\endgroup\$ – Simon Forsberg Aug 1 '14 at 19:43
  • \$\begingroup\$ @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. \$\endgroup\$ – Pimgd Aug 1 '14 at 19:45
  • \$\begingroup\$ @SimonAndréForsberg Oh wait, I made a mistake, because input[1] is in the for loop it CAN be needed multiple times! \$\endgroup\$ – Pimgd Aug 1 '14 at 19:51
1
\$\begingroup\$

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)\$

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.