4
\$\begingroup\$

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 < R

Code

int main() { long long int l, r, k; cin>>l>>r>>k; int lValue=l*k; int numberofElemtsin_l_Range=k+lValue/r - lValue/(l*r); if(numberofElemtsin_l_Range>=k) { int i, j; for(i=numberofElemtsin_l_Range, j=lValue; i>=k; j--) { if(j%l==0 || j%r==0) i--; } cout<<j+1; } else { int rValue = rValue*k; int numberofElemtsin_R_Range= k + rValue/l - rValue/(l*r); if(numberofElemtsin_l_Range>=k) { int i, j; for(i=numberofElemtsin_R_Range, j=rValue; i>=k; j--) { if(j%l==0 || j%r==0) i--; } cout<<j+1; } } return 0; }
\$\endgroup\$

2 Answers 2

Reset to default
3
\$\begingroup\$

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 < 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, // <-- 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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Sorry, I'm not able to follow this without a clean final formula or a piece of c++ code. I have the strong suspicion that your blocksize concept is not sound. \$\endgroup\$ Commented Sep 11, 2017 at 11:25
3
\$\begingroup\$

First - it does not compile.

#include <iostream> using namespace std;

makes the code compile an run, although you should not use namespaces that way.

Second - you mix i/o and functionality

that makes the code less structured and readable. also you cannot easyly unit test it. you should structure the code like

long long int kth = kth_element(long long int l, long long int r, long long int k) { .... return ...; } int main() { long long int l, r, k; cin>>l>>r>>k; long long int kth = kth_element(l, r, k); std::cout << kth; }

that way you have an easily testable function.

Third - be consistent in data types

you use long long int as initial data type suggesting that you handle big numbers. then you use standard int types in your algorithm. that will fail for big numbers. one way to help avoiding such issues is to define a type for that

using Range = long long int; Range kth_element(Range l, Range r, Range k) { ...

Fourth - enable warnings in your compiler and take them seriously

this will help to prevent errors like the range loss named above.

Fifth - test your code with generated test cases

If you had tested your code reasoably you would have noticed that it does not do it's job. Make up all regular and edge cases you can think of and write tests. you should get familiar with some unit test framework (e. g. boost::test). in between you could write a simple test function like 

#include <cassert> void test(Range l, Range r, Range k, Range m) { // l, r, k, expected result m std::cout << l << ","; std::cout << r << ","; std::cout << k << "=="; std::cout << m << " "; std::cout << kth_element_ref(l,r,k) << " "; std::cout << kth_element(l,r,k) << std::endl; assert(kth_element(l,r,k)==m); }

which you use like

int main() { ... test(3,6,2,6); ...

resulting in

3,6,2==6 3 main: main.cpp:70: void test(Range, Range, Range, Range): Assertion `kth_element(l,r,k)==m' failed.
\$\endgroup\$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.