Count Unique Jumps — Problem Statement & Solution Guide
RecursionMediumMixed
TimeO(2^n)
|SpaceO(n)
Problem Description
Given a target system n and jump sizes of 3 or 5, calculate the number of unique sequences of jumps to reach n.
Examples
Example 1
Input
27
Output
2
Explanation: Step-by-step: To reach 27, we can use the sequence 5,5,5,5,5,5,3. We can also use the sequence 3,3,3,3,3,3,5,5. Therefore, the total number of unique sequences is 2.
Example 2
Input
10
Output
3
Explanation: Step-by-step: To reach 10, we can use the sequence 3,3,3,1. However, this sequence is not valid because it contains a jump of 1, which is not allowed. Therefore, we can use the sequences 3,3,3,3,3,3,5,5 or 5,5. Therefore, the total number of unique sequences is 3.
Constraints
- {"name":"n","type":"integer","minimum":1,"maximum":100}
Verified Code Solutions
No solution currently available for JavaScript. Select another language tab above.
public int countUniqueJumps(int n) {
if (n == 0) {
return 1;
} else if (n < 0) {
return 0;
} else {
return countUniqueJumps(n-3) + countUniqueJumps(n-5);
}
}def count_unique_jumps(n):
if n == 0:
return 1
elif n < 0:
return 0
else:
return count_unique_jumps(n-3) + count_unique_jumps(n-5)Asked in Top Tech Interviews
Oracle
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.