Count Unique Jumps — Problem Statement & Solution Guide

RecursionMediumMixed

TimeO(target)

SpaceO(target)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Recursion and solve the Count Unique Jumps problem optimally.

TopicRecursion

PatternMixed

TimeO(target)

SpaceO(target)

Problem Description

Given a non‑negative integer target, you start at position 0. In each move you may advance exactly 3 units or exactly 5 units. Count how many different ordered sequences of moves sum to exactly target. The order of moves matters, so [3,5] and [5,3] are distinct. If no combination reaches target, return 0. The empty sequence is valid when target is 0.

DSA Pattern Breakdown

"Count Unique Jumps"

medium

WHY DOES IT MATTER?

Counting ordered compositions with fixed step sizes appears in many combinatorial DP problems; mastering this pattern teaches you how to convert exponential recursion into linear DP by exploiting overlapping sub‑problems.

OPTIMIZATION CHALLENGE

The key insight is recognizing that the state depends only on the last five targets, allowing the recurrence to be computed iteratively and, if needed, accelerated with matrix exponentiation for logarithmic time.

REAL-WORLD CONNECTION

Think of a network packet that can be split into fragments of 3 KB or 5 KB; the number of ways to assemble a payload of a given size mirrors this jump‑counting problem, informing buffer allocation strategies.

When coding, write the DP loop bottom‑up, initialize dp[0]=1, and guard array accesses with n>=3 or n>=5 checks; this eliminates the need for explicit recursion and avoids stack overflow on large inputs.

COMPLEXITY AT A GLANCE

⏱ Time:O(target)

💾 Space:O(target)

Core Theory — Why This Approach?

The problem asks for the number of ordered sequences of moves of length 3 or 5 that sum to a given target. This is a classic example of counting compositions with restricted part sizes, which naturally leads to a recurrence relation: let f(n) be the answer for target n, then f(n)=f(n-3)+f(n-5) because any valid sequence ending at n must end with either a 3‑step or a 5‑step. The base case f(0)=1 (the empty sequence) and f(n<0)=0. A naïve recursive implementation explores both branches at every level, yielding an exponential O(2^{n/3}) time complexity due to massive overlapping sub‑problems. By recognizing the overlapping sub‑structure, we can apply memoization or bottom‑up dynamic programming to store previously computed f values, collapsing the exponential tree into a linear scan over the target range. This transforms the solution into an optimal O(target) time algorithm with O(target) auxiliary space (or O(1) space if we keep only the last five values).

Interview Questions on This Problem

Q1How would you modify the solution if the allowed jumps were 2, 4, and 7 instead of 3 and 5?

The recurrence generalizes to f(n)=f(n-2)+f(n-4)+f(n-7) with the same base cases; you would simply extend the DP array to consider the three offsets and still achieve O(n) time.

Q2Can you derive a closed‑form formula for the number of sequences for large targets?

Because the recurrence is linear with constant coefficients, its characteristic equation x^5 = x^2 + 1 can be solved; the solution is a linear combination of the roots raised to the power n, but in practice the DP approach is preferred due to integer overflow and precision concerns.

Q3What is the time‑space trade‑off if the target can be as large as 10^9?

For very large targets you can use matrix exponentiation on the recurrence vector of size 5 to compute f(n) in O(log n) time and O(1) space, at the cost of handling big integers or modular arithmetic.

Examples

Example 1

Input

Output

Explanation: No moves are needed; the empty sequence counts as one valid way.

Example 2

Input

Output

Explanation: The only ways to reach 8 are [3,5] and [5,3]; thus two distinct sequences.

Example 3

Input

Output

Explanation: 14 can be expressed as 3+3+3+5. There are 4 moves in total, with three 3‑steps and one 5‑step. The number of permutations is 4!/(3!·1!) = 4, giving the sequences [3,3,3,5], [3,3,5,3], [3,5,3,3], [5,3,3,3].

Constraints

0 <= target <= 10^9
Result fits in a 64‑bit signed integer
Only step sizes 3 and 5 are allowed

Optimal Approach & Strategy

Use a bottom‑up DP array where dp[i] = dp[i‑3] + dp[i‑5]; fill it from 0 to target, returning dp[target]. This runs in linear time and uses linear (or constant) extra space.

Brute Force Approach

Recursively try every possible next jump (3 or 5) until the sum reaches or exceeds the target, counting a path only when it hits the target exactly. This explores a binary tree of depth ≈target/3, leading to exponential time.

Code Solutions

Language:

JavaScript Solution

Time: O(target)

function countUniqueJumps(target){
    if(target<0) return 0;
    const dp=new Array(target+1).fill(0);
    dp[0]=1;
    for(let i=1;i<=target;i++){
        let ways=0;
        if(i>=3) ways+=dp[i-3];
        if(i>=5) ways+=dp[i-5];
        dp[i]=ways;
    }
    return dp[target];
}

const fs=require('fs');
const input=fs.readFileSync(0,'utf8').trim();
if(input.length){
    const t=parseInt(input,10);
    console.log(countUniqueJumps(t));
}

#include <bits/stdc++.h>
using namespace std;

long long countUniqueJumps(int target) {
    if (target < 0) return 0;
    vector<long long> dp(target+1,0);
    dp[0]=1;
    for(int i=1;i<=target;++i){
        long long ways=0;
        if(i>=3) ways+=dp[i-3];
        if(i>=5) ways+=dp[i-5];
        dp[i]=ways;
    }
    return dp[target];
}

int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;while(cin>>t){cout<<countUniqueJumps(t); if(!cin.eof()) cout<<"\n";}return 0;}

import java.io.*;
import java.util.*;

public class Main {
    public static long countUniqueJumps(int target) {
        if (target < 0) return 0L;
        long[] dp = new long[target+1];
        dp[0] = 1L;
        for (int i = 1; i <= target; i++) {
            long ways = 0L;
            if (i >= 3) ways += dp[i-3];
            if (i >= 5) ways += dp[i-5];
            dp[i] = ways;
        }
        return dp[target];
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if (line == null || line.isEmpty()) return;
        int target = Integer.parseInt(line.trim());
        System.out.println(countUniqueJumps(target));
    }
}

def countUniqueJumps(target:int)->int:
    if target<0:
        return 0
    dp=[0]*(target+1)
    dp[0]=1
    for i in range(1,target+1):
        ways=0
        if i>=3:
            ways+=dp[i-3]
        if i>=5:
            ways+=dp[i-5]
        dp[i]=ways
    return dp[target]

if __name__=="__main__":
    import sys
    data=sys.stdin.read().strip()
    if data:
        t=int(data)
        print(countUniqueJumps(t))

function countUniqueJumps(target){
    if(target<0) return 0;
    const dp=new Array(target+1).fill(0);
    dp[0]=1;
    for(let i=1;i<=target;i++){
        let ways=0;
        if(i>=3) ways+=dp[i-3];
        if(i>=5) ways+=dp[i-5];
        dp[i]=ways;
    }
    return dp[target];
}

const fs=require('fs');
const input=fs.readFileSync(0,'utf8').trim();
if(input.length){
    const t=parseInt(input,10);
    console.log(countUniqueJumps(t));
}

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.