754. Reach a Number

Let's make this one less mysterious. For 754. Reach a Number, the solution in this repository is mainly a straightforward implementation solution.

Guide

What?

Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:

What state are we keeping?
How do we move from one state to the next?
When do we know the answer is already determined?

For this file, the main tools are: straightforward implementation.

The notes already sitting in the source point us in the right direction:

Guide

When?

Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.

The important function names to track are reachNumber.

Guide

Why?

The solution works because it narrows the problem until every update has a clear reason to exist.

The queue gives the solution a level-by-level or frontier-style traversal.
The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.

Guide

How?

Walk through the solution in this order:

Initialize the memory or helper structure.
Process candidates in the order the invariant expects.
Update the answer only when the current state is valid.
Return the value that represents the fully processed input.

The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.

Guide

Complexity

Time: O(sqrt(target)), the iteration count of while loop, (1+2+...+move) = (1+move)*move/2 >= target
Space: O(1)

Guide

C++ Solution

Your submission

The accepted solution

solution.cpp

01//TLE
02struct Node{
03    long long cur;
04    long long move;
05    Node(){};
06    Node(long long c, long long m){
07        cur = c;
08        move = m;
09    };
10};
11
12class Solution {
13public:
14    int reachNumber(int target) {
15        queue<Node> q;
16        q.push(Node((long long)0, (long long)1));
17        Node n;
18            
19        while(!q.empty()){
20            n = q.front();
21            q.pop();
22            
23            if(n.cur == target){
24                //moves taken
25                return n.move-1;
26            }
27            
28            q.push(Node(n.cur+n.move, n.move+1));
29            q.push(Node(n.cur-n.move, n.move+1));
30        }
31        
32        return -1;
33    }
34};
35
36//solution
37//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Reach a Number.
38//Memory Usage: 8.1 MB, less than 100.00% of C++ online submissions for Reach a Number.
39//time: O(sqrt(target)), the iteration count of while loop, (1+2+...+move) = (1+move)*move/2 >= target
40//the while loop execute O(move) times, equal to O(log(target)) times
41//space: O(1)
42
43class Solution {
44public:
45    int reachNumber(int target) {
46        target = abs(target);
47        int sum = 0, move = 1;
48        while(sum < target){
49            sum += move;
50            move++;
51        }
52        move--;
53        int delta = sum - target;
54        //if delta is even, we can make one move negative so the sum will be target
55        if(delta % 2 == 0) return move;
56        //if delta is odd
57        // we go one more step: move+1(odd), now delta become even
58        // if move+1 is even, we need to go move+2 steps
59        return move + 1 + move%2;
60    }
61};

Cost

Complexity

Time

O(sqrt(target)), the iteration count of while loop, (1+2+...+move) = (1+move)*move/2 >= target

Dominated by the main traversal, recursion, or data-structure operations in the code.

Space

O(1)

Auxiliary state plus the answer structure where the problem requires one.