Find a given number is reachable or not
There is number line ranging from -infinity to +infinity. Initially you are number 0. you can move in both directions(Moving left would decrease the number and moving right would increase the number). The condition is that in the ith step you have to iterate i numbers only, you can not stop in the middle. Now you have to tell that, whether a given number is reachable or not.
For example you can reach number 2 in following steps (0,1), (1,-1), (-1,2).
Also you need to provide the optimal solution to reach a given number if its reachable.
We can approach this problem by realizing that we can reach any integer n by making repeated jumps of size 1, alternating between moving to the left and moving to the right. Specifically, to reach n, we can make the following jumps:
- Move 1 unit to the right
- Move 2 units to the left
- Move 3 units to the right
- Move 4 units to the left
- Move 5 units to the right
- Move 6 units to the left
- and so on, continuing to alternate directions and increasing the size of the jump by 1 each time
This sequence of jumps will eventually reach n, since the sum of the jump sizes is 1 – 2 + 3 – 4 + 5 – 6 + … = 1 + (3 – 2) + (5 – 4) + (7 – 6) + … is an infinite series that diverges to infinity.
To find the optimal solution to reach a given number n, we can first check if it is reachable by computing the sum of the first k integers, where k is the smallest positive integer such that n is less than or equal to the sum. If n is not reachable, we can stop and return “not reachable”. Otherwise, we can find the sequence of jumps as follows:
- Start at 0
- Move 1 unit to the right
- Move 2 units to the left, unless we have already reached n
- Move 3 units to the right, unless we have already reached n
- Move 4 units to the left, unless we have already reached n
- Continue alternating between left and right, increasing the jump size by 1 each time, until we reach n.
This algorithm will terminate after at most 2n steps, since the sum of the jump sizes is at most 1 + 2 + … + n = n(n+1)/2. Therefore, it provides an optimal solution to reach a given number if it is reachable.
Your Answer
More puzzles to try-
Filling Box
Sam keeps marbles in a box everyday in such a way that the number of marbles in the box doubles ...Read More »Finding a restaurant in a park
A park contains paths that intersect at various places. The intersections all have the properties that they are 3-way intersections ...Read More »James Bond Archer
James Bond is caught up in a mysterious scenario where the evil villain has him blindfolded. He somehow breaks through ...Read More »Last Letter
What is the last letter to this sequence and why JFMAMJJASON….?Read More »Most Difficult Induction Teaser
A teacher decides to give a pop quiz one day but all of her students refuse to take the quiz ...Read More »Next Number in Series
Find the next number in the series below 21 32 54 87 131 ?Read More »I Always Lie
I am lying and I always lie. Tell me whether I am lying or telling the truth.Read More »Excuse me everyone, Please find the meaning of this riddle
Can you find out the meaning of this riddle? ABCDEFGHIJKLMNOPQRSTUVWYZ QQQQQQQQQQQQQQQQQQQQQQQQQRead More »One digit number
What two whole, positive numbers that have a one-digit answer when multiplied and a two-digit answer when added?Read More »Look as flat
It come across as flat, But theirs more to it than its surface; You climb its mountains from top to ...Read More »Never resting, never still
Never resting, never still, Moving silently from hill to hill. It does not walk, run or trot, All is cool ...Read More »Olympic Play riddle
At last month’s rehearsal, four top athletes competed in two qualifying 200 meter races. As the results were expected to ...Read More »Sitting Arrangement
Eight friends – Nancy, Harris, Jim, Feona, Daniel, Tony, Mary and Susan are sitting around a circular table. Susan is ...Read More »No. of letters are in the alphabet
How many letters are in the alphabet ?Read More »You throw away the outside and cook the inside riddle
You throw away the outside and cook the inside. Then you eat the outside and throw away the inside. What ...Read More »Genie with c hats and n men puzzle
A bunch of men are on an island, A genie comes down and gathers everyone together and places a magical ...Read More »What is the smallest possible amount of money ?
A grocer in a small business had managed to put aside (apart from his legitimate profits) little sum in dollar bills, ...Read More »34+89=400 Matchstick Equation Puzzle
Correct the equation by moving one matchstick 34+89=400 As given in the matchstick equation (34+89=400) in the above diagram, move ...Read More »Sky and Ocean
I am four letters long. I can be seen in the sky, I am the ocean & I am the ...Read More »Who Honks
Who can Honk without using a Horn? A) Goose B) Crane C) Penguin D) HummingRead More »