Help
Given two natural numbers N and K where N >= 2, you have a list of available numbers as all numbers in inclusive range K to K+N-1. You can sum any two natural numbers in available list to create a new natural number, which is then added to list of available numbers. How many natural number exist which cannot be created by this method?
I'm tempted to say none.
Pick a number. Let's say 18743286432987543895.
I can make that easily. My starting values are K=2 and N=7584750849753846743087565784367894.
That means my list is every number from 2 to 7584750849753846743087565784367894 + 2 - 1, which contains that first number.
Basically, there is no number you can name that I cannot get onto my list, because I just pick my starting values to be 2 and some number bigger than your number.
Or are you saying that you get a given a set, fixed N and K, and you have to identify all the numbers that cannot be added to the list for that particular N and K?
Last edited on
With n=2 and k=6, here are the numbers you can get:
2,3,4,5,6,7 to begin with.
Now you can get all remaining numbers to infinity, by adding 2 to the second highest number in your list, forever.
2 +6 = 8
2 +7 = 9
2 + 8 = 10
2 + 9 = 11
2 + 10 = 12
and so on.
So with the numbers n=2 and k=6, you can get every positive integer from 2 to infinity.
2,3,4,5,6,7 to begin with.
Now you can get all remaining numbers to infinity, by adding 2 to the second highest number in your list, forever.
2 +6 = 8
2 +7 = 9
2 + 8 = 10
2 + 9 = 11
2 + 10 = 12
and so on.
So with the numbers n=2 and k=6, you can get every positive integer from 2 to infinity.
this is wrong i think..
We have a range k to k+n-1 both inclusive,i.e,6 and 7.
So why we are starting from 2?
here is the link to the question..
https://www.codechef.com/JUNE19B/problems/CHFING
We have a range k to k+n-1 both inclusive,i.e,6 and 7.
So why we are starting from 2?
here is the link to the question..
https://www.codechef.com/JUNE19B/problems/CHFING
Last edited on
Oh, right. I assumed that it didn't matter which was n and which was k, so I just swapped them round. I thought this was a number theory question, but it seems it's another codechef.
I think thats a problem from an ongoing contest.....use a pen and a paper and write down answers for 2 or 3 examples you will see a pattern....give it time if u want to learn!!
6 7 12 13 14 18 19 20 21 24 25 26 27 28 30 31 32 33 34 35....(rest all)
So number of missing numbers are 5+4+3+2+1
I guess that explains a lot!!
So number of missing numbers are 5+4+3+2+1
I guess that explains a lot!!
Last edited on
| So number of missing numbers are in these.... |
So what's the answer? (And can't you make 12 and 14, for example?)
Last edited on
@iotaa yes sure....i missed that....i mean to say just keep adding numbers already in the array...and after a while all the numbers will start appearing!!
the pattern is quite simple if you write it down with examples, still I think there is a boundary value of something that is giving me WA in 1 task.
If any of you guys have completed the problem, can you provide some inputs and there right outputs, like large values and such?
If any of you guys have completed the problem, can you provide some inputs and there right outputs, like large values and such?
Last edited on