Đến vị trí mục tiêu trên đường số trong C++

Giả sử bạn đang đứng tại vị trí 0 trên một đường số vô hạn. Mục tiêu nằm tại vị trí target. Ở mỗi bước di chuyển, bạn có thể đi sang trái hoặc sang phải. Tại bước thứ n (bắt đầu từ 1), bạn đi đúng n bước. Bài toán yêu cầu tìm số bước tối thiểu để đến đích.

Ví dụ: target = 3 cần 2 bước. Từ 0 đến 1 (bước 1), từ 1 đến 3 (bước 2).

Thuật toán

1. Lấy giá trị tuyệt đối: target = |target|, khởi tạo cnt = 0.
2. Khi target > 0:
   • Tăng cnt lên 1.
   • Trừ cnt khỏi target.
3. Nếu target chẵn, trả về cnt; ngược lại trả về cnt + 1 + cnt % 2.

Mã nguồn C++

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

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int cnt = 0;
        while (target > 0) {
            target -= ++cnt;
        }
        return (target % 2 == 0) ? cnt : cnt + 1 + cnt % 2;
    }
};

int main() {
    Solution ob;
    cout << ob.reachNumber(3);
    return 0;
}

Đầu vào / Đầu ra

Input: 3

Output: 2