- Forum
- General C++ Programming
- findind kth no for multiiples of three
findind kth no for multiiples of three no set ...internship questn
given A,B,C ..there is a special set contains the no that are multiple of any of thse no ..we have to deteremine the kth no of that set..
constraints..
A,B,C <=1e4;
k<=1e12
test case...
i/p :1 2 3 4
o/p : 4
i.p:2 4 5 5
o/p: 8
A good way of getting help in ANY walk of life is to show that you're struggling before asking for help. To struggle, you need to actually try to do something.
If you post code that you've written so far and it's anything more than a bare skeleton, that'll be more likely to get you help.
That said, this is a codechef problem, and I'm pretty sure it's against the spirit (and/or rules) of that site to get help from other people to boost your rank, so... good luck!
-Albatross
If you post code that you've written so far and it's anything more than a bare skeleton, that'll be more likely to get you help.
That said, this is a codechef problem, and I'm pretty sure it's against the spirit (and/or rules) of that site to get help from other people to boost your rank, so... good luck!
-Albatross
You put in ZERO effort to solve the problem yourself by writing code, so we put in ZERO effort to help you.
Unless you want to PAY money for "the solution."
I doubt you can afford what it would cost, though.
Unless you want to PAY money for "the solution."
I doubt you can afford what it would cost, though.
> internship questn
Do you think whoever is offering you a prospective position would want someone who's basically trying to scam their way into the organisation.
Do you think whoever is offering you a prospective position would want someone who's basically trying to scam their way into the organisation.
Work the problem backwards. Let's do a simple example.
Suppose there are only 2 number (A and B). They are 3 and 5. Now pick a number X.
How many numbers k are in the set of numbers less than X?
There are X/3 multiples of 3 and X/5 multiples of 5.
But that double counts some numbers like 15 and 30 because they are divisible by 3 AND 5. More specifically, it double counts the multiples of 3*5=15.
So the total number in the set is X/3 + X/5 - X/15.
Now extend this reasoning for 3 numbers A,B,C.
Now you can write a function that finds k when given A,B,C and X:
Now you can do a binary search to find X for a given K.
The biggest problem with this approach is that you might overflow
Suppose there are only 2 number (A and B). They are 3 and 5. Now pick a number X.
How many numbers k are in the set of numbers less than X?
There are X/3 multiples of 3 and X/5 multiples of 5.
But that double counts some numbers like 15 and 30 because they are divisible by 3 AND 5. More specifically, it double counts the multiples of 3*5=15.
So the total number in the set is X/3 + X/5 - X/15.
Now extend this reasoning for 3 numbers A,B,C.
Now you can write a function that finds k when given A,B,C and X:
unsigned findK(unsigned A, unsigned B, unsigned C, long long X);Now you can do a binary search to find X for a given K.
The biggest problem with this approach is that you might overflow
Topic archived. No new replies allowed.