May be you can look at the problem from whole another angle.
- 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).
- think you your table as sorted arrays, so is there really need to sort again(even for merged array)?
- do we really need to generate the whole tables?
here how I would try to solve this (without generating the whole array/any sequence).
- 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)
- 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)
- 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