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-
Difference between minute and hour hands.
If the difference between hour and minute hand is 6 minutes then after how much time the difference will be 7 ...Read More »Count the Triangle Puzzle
Solve the counting riddle by identifying the number of triangles in the given picture.Read More »Open his jaws
Poke your fingers in his eyes and he will open wide his jaws. Linen cloth, quills, or paper, his greedy ...Read More »Can you name it ?
There is a five letter word which has 3 consonants(all are same) and 2 different vowels. Also something wrong associated ...Read More »Arrange the Puppets
Sweet & very intelligent katty has 8 puppets(Jane Bird Barbie Angel Colleen Nora Lass Missy). All puppets are of different ...Read More »12 dollar riddle
My goal is to have $12. If I save $1 a month then it will take me 12 months to ...Read More »Identify the kidnapper
Look carefully in the picture below. Can you identify who is the kidnapper?Read More »Get wetter the more it dries riddle
What gets wetter and wetter the more it dries?Read More »Rocking Chair
What we call when we combine roller skates & a rocking chair.Read More »Measure the Water
Suppose you are sitting in an interview and the interviewee asks you an aptitude question. You have three buckets with ...Read More »Tricky Password Mystery Problem
A brother wants to use his brother’s desktop computer. When he opens it, he finds out that it is password ...Read More »who has doesn’t keep
The one who has it does not keep it. It is large and small. It is any shape.Read More »Remove or fill
I am white, and used for cutting and grinding. When I am damaged, humans usually remove me or fill me. ...Read More »Mark my name
I have a very good name to tell, Mark my words, and Mark them well. I have said it twice, ...Read More »Ice cream parlor brain teaser
Two women and two doctors walk into an ice cream parlor. Their favorite flavour was strawberry. Unfortunately, the parlor didn’t have much ...Read More »Dog bite
Male: Does your dog bite? Female: No All of a sudden the dog bites the male on his leg. Yet ...Read More »A,B,C ology puzzle
Astrology starts with the alphabet A. Biology starts with the alphabet B. Limnology starts with the alphabet L. Can you ...Read More »Who killed Child 2, Investigation Puzzle
Four children having five rocks each were playing a game in which they had to throw the rock at particular ...Read More »The Bacteriologist
A scientist is experimenting with bacteria that are one micron in diameter and that reproduce by dividing every minute into ...Read More »Fingers Multiplication tricky puzzle
Assume there are approximately 5,000,000,000 (5 billion) people on Earth living presently. What would you estimate to be the result, ...Read More »