Find the kth element which is either divisible by l or r or both This was asked to me in one of interview, so can someone please have a look is my code efficient or we can further improve it.

Example

Input  l=2 r=3 k=10

Output:  15 


Explanation 15 is at the 10 position of number divisible by 2 or 3 or both.

{2, 3, 4, 6, 8, 9, 10, 12, 14, 15} 15 is at 10th position.

Assumption: L &lt; R

Code

int main()
{
    long long int l, r, k;
    cin&gt;&gt;l&gt;&gt;r&gt;&gt;k;
    int lValue=l*k;
    int numberofElemtsin_l_Range=k+lValue/r - lValue/(l*r);
    if(numberofElemtsin_l_Range&gt;=k)
    {
        int i, j;
        for(i=numberofElemtsin_l_Range, j=lValue; i&gt;=k; j--)
        {
            if(j%l==0 || j%r==0) i--;
        }
        cout&lt;&lt;j+1;
    }
    else
    {
        int rValue = rValue*k;
        int numberofElemtsin_R_Range= k + rValue/l - rValue/(l*r);
        if(numberofElemtsin_l_Range&gt;=k)
        {
            int i, j;
            for(i=numberofElemtsin_R_Range, j=rValue; i&gt;=k; j--)
            {
               if(j%l==0 || j%r==0) i--;
            }
            cout&lt;&lt;j+1;
        }
    }
    return 0;
}
First, there's a couple of things you're not doing which I think you should: you should provide a comment describing what this program does, and you should validate your inputs.

That is, give a banner like:

/* Given inputs L, R, and K, print the Kth element of the sequence 
   of integers made up of all positive multiples of L and/or R, in
   ascending order. */


And validate the inputs with an assert, an error message, or just by swapping L and R if they're not in order. Also, ensure the numbers are positive.

Another approach

With that said, I'd like to encourage you to think about the problem a different way: assuming that L &lt; R, what happens when you add a multiple of R in the sequence?

Let's use 5 and 11 instead of 2 and 3, because they have a bunch of problems and they produce numbers that are all fairly distinct when you divide them. (They're a better example than 2 and 3, or 3 and 7 which were the first two examples I tried. ;-)

If you have L=5, R=11, K=10, consider adding a multiple of R to the sequence:

sequence = {}                // empty sequence
add a multiple of R          // R is 11, remember
sequence = {5, 10, 11}


We'll call that a "block". Adding a "block" adds all the numbers up to the next multiple of R.

Each multiple of 11 brings with it 11/5 = 2+1/5 multiples of 5, because 11/5 == 2+1/5. But when the fractions finally add up to a whole number, it won't count! That's when the multiple of 11 will also be a multiple of 5 (55, 110, 165, etc.) and the numbers aren't added to the sequence more than once. So really, adding a multiple of 11 to the sequence adds 1 (the multiple of 11) plus floor(11/5) == 2 multiples of 5 to the sequence. 

In general, adding a "block" -- that is, adding one multiple of R -- to the sequence adds 1 + floor(R/L) numbers to the sequence. We'll call that the "block size" or blocksize.

blocksize = 1 + int(R/L);


We can use this in reverse: If K=10, as above, then K/blocksize == K/3 == 3 (remainder 1). So the 10th value in the sequence would be 3 blocks plus one non-block number. That is:

sequence = {
    /*block 1*/ 5, 10,11,
    /*block 2*/ 15,20,22,
    /*block 3*/ 25,30,33,
    /*block 4*/ 35,         // &lt;-- K=10th number
                   40,44,
    /*block 5*/ 45,50,55,
    /*block 6*/ 60,65,66,
}


The only tricky part will be finding the fractional-block numbers, since you can't just add 5 to 33. 

This leaves us with two cases: the cases where K is a multiple of the block size, and cases where there is a remainder.

If K is a multiple of the block size, then the result is simply

R * (K/blocksize)


For the 9th number in the sequence, we'd have K/blocksize == 3, and R * 3 == 33, as shown above.

If K is not a multiple of the block size, we have to find a multiple of L that is less than or equal to the highest number in the previous block, then add L * remainder(K/blocksize) to it. 

So if K=10, as above, we look for the multiple of L (5) that is less than or equal to the highest number in block 3. 3 * R == 33, so we'd use 30, then add remainder(10/3) == 1 multiple of 5: 30 + 1*5 = 35.

Similarly, if K=17, we would find the highest multiple of 5 less than or equal to 55, which of course is 55. Then we'd add remainder(17/3) == 2 multiples of L, or 2 * 5, to get 65.

The upshot of this is that you can find your result directly, with just a few integer operations, no looping required.