Race Car - Practice Coding Problems

Race Car - Problem

Dynamic Programming Hard

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions.

Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse):

When you get instruction 'A', your car does the following:
position += speed
speed *= 2
When you get instruction 'R', your car does the following:
If your speed is positive then speed = -1
Otherwise speed = 1
Your position stays the same.

For example, after commands "AAR", your car goes to positions 0 → 1 → 3 → 3, and your speed goes to 1 → 2 → 4 → -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.

Input & Output

Example 1 — Target at 3

$ Input: target = 3

› Output: 2

💡 Note: Start at position 0, speed 1. First 'A': position becomes 0+1=1, speed becomes 1×2=2. Second 'A': position becomes 1+2=3, speed becomes 2×2=4. We reach target 3 in 2 steps: "AA"

Example 2 — Target at 6

$ Input: target = 6

› Output: 5

💡 Note: Optimal sequence is "AAARA": A(1,2) → A(3,4) → A(7,8) → R(7,-1) → A(6,2). This takes 5 steps to reach target 6

Example 3 — Target at 1

$ Input: target = 1

› Output: 1

💡 Note: Just one 'A' instruction: position becomes 0+1=1, which is the target. Only 1 step needed

Constraints

1 ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Start

Car at position 0, speed 1

Instructions

A: move forward and double speed, R: reverse direction

Goal

Find shortest sequence to reach target

Key Takeaway

🎯 Key Insight: Model as shortest path problem where BFS guarantees minimum steps to target

Asked in

G Google 45 f Facebook 30 a Amazon 25

The key insight is to model this as a shortest path problem where each state is (position, speed). The optimal approach uses BFS to explore states level by level, guaranteeing the shortest sequence. Time: O(T × log T), Space: O(T × log T)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Sequences	O(2ⁿ)	O(n)	Generate all possible sequences of A and R until target is reached
BFS - Shortest Path	O(T × log T)	O(T × log T)	Use BFS to find shortest sequence of instructions level by level
Memoization - Cache Results	O(T × log T)	O(T × log T)	Use recursion with memoization to avoid recomputing same states

Brute Force - Try All Sequences — Algorithm Steps

Start from position 0, speed 1
For each state, try both 'A' and 'R' operations
Recursively explore all paths until target is found
Return the minimum sequence length

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Position 0, Speed 1

Branch

Try both A (accelerate) and R (reverse)

Recurse

Continue until target found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int min_val(int a, int b) {
    return a < b ? a : b;
}

int dfs(int pos, int speed, int steps, int target) {
    if (pos == target) {
        return steps;
    }
    if (abs_val(pos) > 2 * abs_val(target) || steps > 20) {
        return INT_MAX;
    }
    
    // Try accelerate
    int result1 = dfs(pos + speed, speed * 2, steps + 1, target);
    
    // Try reverse
    int newSpeed = speed > 0 ? -1 : 1;
    int result2 = dfs(pos, newSpeed, steps + 1, target);
    
    return min_val(result1, result2);
}

int solution(int target) {
    return dfs(0, 1, 0, target);
}

int main() {
    int target;
    scanf("%d", &target);
    printf("%d\n", solution(target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each position has 2 choices (A or R), creating exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion stack can go n levels deep where n is the answer

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Sequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler