หาจำนวนขั้นตอนน้อยที่สุดเพื่อไปถึงเป้าหมายบนเส้นจำนวนใน C++

สมมติว่าคุณยืนอยู่ที่ตำแหน่ง 0 บนเส้นจำนวนอนันต์ โดยมีเป้าหมายอยู่ที่ตำแหน่ง target ในแต่ละขั้นตอนที่ n (เริ่มจาก 1) คุณสามารถเดินไปทางซ้ายหรือขวาได้ n ก้าว เราต้องหาจำนวนขั้นตอนน้อยที่สุดที่จำเป็นเพื่อไปถึงจุดหมาย

ตัวอย่างเช่น หาก target = 3 จำเป็นต้องใช้ 2 ขั้นตอน: จาก 0 ไป 1 แล้วจาก 1 ไป 3

วิธีแก้ปัญหา

1. กำหนด target = |target|, cnt = 0
2. วนลูป while target > 0:
   • เพิ่ม cnt ขึ้น 1
   • ลด target ลง cnt
3. หาก target เป็นเลขคู่ ให้คืนค่า cnt มิฉะนั้นคืนค่า cnt + 1 + cnt % 2

ตัวอย่างโค้ด 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;
}

Input

3

Output

2