Click here to Skip to main content
15,395,859 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Panda is very fond of bouncing on the rocks. Some rocks n are placed in a forest. Rocks contain some springs attached to them. The number of springs on a rock is directly proportional to the panda's maximum bounce length. A number of springs attached to each of the rocks are given. Each number indicates the maximum length of bounce at that position.

Panda is starting from the first rock. The destination is to reach the last rock. Find out if the panda will meet the destination or not.

(Number of springs can't be negative)


__________________________________________________________________________________
Input

The first line contains n, denoting the number of rocks.
The Second line contains the number of springs attached to each of the n rocks.
__________________________________________________________________________________

CONSTRAINTS

1 ≤ n ≤ 1000
0 ≤ springs ≤ 100000

__________________________________________________________________________________

Output

Return true if panda can reach the destination, otherwise false

__________________________________________________________________________________

SAMPLE INPUT 1

7
2 5 1 1 7 4 9

SAMPLE OUTPUT 1

true

EXPLANATION 1

Panda will first bounce from rock 1 to 2, then after 5 bounces, he will reach the destination.

__________________________________________________________________________________

SAMPLE INPUT 2

4
1 1 0 4

SAMPLE OUTPUT 2

false

EXPLANATION

In this case, panda will never be able to reach the destination.

What I have tried:

I couldn't get any solution to the above problem. Is there an optimized solution?
Posted
Updated 4-Jun-22 9:51am
Comments
Rick York 4-Jun-22 0:20am
   
Yes.
merano99 4-Jun-22 14:37pm
   
SAMPLE INPUT 1

7
Springs: 2 5 1 7 4 9
Rock no: 1 2 3 4 5 6 7

Where exactly is the target?
Shouldn't the panda be at the target here after 4 jumps?
From 1-3, 3-4, 4-5, 5-Target

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
   
Comments
Kashif Farhaan 4-Jun-22 1:21am
   
Alright, can I get a hint on what method/technique(backtracking, hashing, etc.) I need to use? I can't figure out even a brute force solution to this problem. And no, I'm not getting paid for this. This is a legit interview question I came across yesterday while writing a test called NCET.
OriginalGriff 4-Jun-22 1:38am
   
The idea of an interview question is not that you submit "my solution" - it's that they get to see how you think. How you work. What exactly you can do.

And to be honest, if you can't solve this on your own, then they need to know that as it means you probably can't do the actual job either, and advancing you to the next interview stage / round would be unfair on you, on the prospective employer, and on the other candidates who were more honest about their abilities!
Quote:
I couldn't get any solution to the above problem.

So I fear you failed the job interview.
Usually, solving the problem manually give hints about the algorithm to use.
Quote:
Is there an optimized solution?

This problem look to come from a challenge site; And for this kind of problem, there is an optimized solution in 90% of cases.
Optimized algorithm may have many meanings as there is usually many degrees of brute force.
   
Each number in the list tells you how many of the next numbers to jump over. So you could start by creating a list of the numbers. You can then move through them starting at the first, and adding each value to the offset of the current one. If you reach or pass the end of the list then the Panda has made it. If not, he/she has not. Note that this would also work for Meerkats.
   
The easiest way would be a recursive solution, which would also help if it does not work with the maximum jump distance.
C++
vector<unsigned> rock{ 2, 5, 1, 1, 7, 4, 9 };
unsigned startpos = 0, jcnt = 0;

bool res = jump(startpos, rock, rock[startpos], jcnt);

cout << "Result: " << ((res) ? "true" : "false") << "Jumps: " << jcnt << "\n";

with:
C++
bool jump(unsigned pos, vector<unsigned> &rock, unsigned jumplen, unsigned &jcnt);
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900