Calculating the Nth number in the supertable of two numbers

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

May be you can look at the problem from whole another angle.

1. the problem with brute force is it will take linear amount of time and memory, which is not affordable(especially when you have better ways to solve the problem).
2. think you your table as sorted arrays, so is there really need to sort again(even for merged array)?
3. do we really need to generate the whole tables?

here how I would try to solve this (without generating the whole array/any sequence).

1. if you want the Nth number in a supertable, lets assume it's just nth number in your first table. (if the another input is 0, it's solved at this point)
2. now the key here is to calculate the displacement of Nth number cause you are merging another table (sorted table). so I would say the displacement of nth number in your supertable is

=nth number in your first table / second number

this will give your the number of items in second table while are smaller than nth number of first tbale. lets say above is value x, so these x digits will appear before your nth number in your supertable. (guess this is obvious as these numbers are smaller than nth number in super table)

3. now we know the our assumption in the step 1 was not quite right and we must choose other number in the first table as valid candidate. since we had already chose the nth number(where no other number from another table are appearing before it) the new number will be less than the nth number. so how do you choose the new nth number I would say use binary search algo. logic.

sample code, it's working for small inputs:

 static Int64 getItem(Int64 number, Int64 numbertwo, Int64 range)
    {            
        var lowerBound = (Int64)1;
        var upperBound = range;
        Int64 lcm = determineLCM(number, numbertwo);

        while(upperBound - lowerBound > 1)
        {
            Int64 limitNumber = number * lowerBound;                
            Int64 itemsInSecondSeries = ((Int64) limitNumber / numbertwo) 
                    - ((Int64)limitNumber / lcm);

            var boundDiff = upperBound - lowerBound;
            if (lowerBound + itemsInSecondSeries >= range)
            {                    
                upperBound = lowerBound;
                lowerBound -= (Int64) boundDiff;
            }
            else if(lowerBound + itemsInSecondSeries < range) {
                lowerBound += (Int64) boundDiff / 2;
            }
            // Console.WriteLine("lower: " + lowerBound + " upper: " + upperBound);
        }

        if(lowerBound + ((Int64)lowerBound * number/numbertwo) 
        - ((Int64)lowerBound * number / lcm)  > range) {
            lowerBound--;
            upperBound--;
        }
        
        var lowerNumber = lowerBound * number;
        var upperNumber = upperBound * number;
        var secondListBound = ((Int64)upperNumber/numbertwo);
        var secondListNumber = secondListBound * numbertwo;
        // Console.WriteLine("lower: "+lowerBound+" upper: " + upperBound +
        // " second: "+secondListBound);            
        if(lowerBound + ((Int64)lowerNumber/numbertwo) 
        - ((Int64)lowerNumber / lcm)  == range)
        {
            return lowerNumber;
        } else if(upperBound + ((Int64)upperNumber/numbertwo) 
        - ((Int64)upperNumber / lcm) == range) {
            return upperNumber;
        }
        else
        {
            return secondListNumber;
        }

        return upperNumber;
    }

Note: we are subtracting the numbers related to LCM cause they will appear in both tables, and we'll include them only once in the super table.

UPDATE: I tested above on huge inputs (from 1000 to 300000 different combinations). It executes under 3 seconds using max memory 122860KB. Think those are good numbers to achieve. You can optimism further by not doing unnecessary conversion and using common variables in above code. But I'll leave it as it is, as it's already giving good numbers. Edits are welcome. :)

Tests can be seen here