จำนวนการเคลื่อนที่น้อยที่สุดเพื่อทำให้ N หาร 25 ลงตัวด้วย C++

ข้อความโจทย์

กำหนดจำนวน N โดยไม่มีศูนย์นำหน้า (Leading Zeros) งานคือหาจำนวนการเคลื่อนที่ขั้นต่ำที่จำเป็นเพื่อทำให้ N หาร 25 ลงตัว ในแต่ละการเคลื่อนที่ สามารถสลับเลขสองตัวที่อยู่ติดกันได้ และต้องแน่ใจว่าในทุกเวลา ตัวเลขต้องไม่มีศูนย์นำหน้า ถ้าไม่สามารถทำให้ N หาร 25 ลงตัวได้ ให้พิมพ์ -1

ถ้า N = 5071 แล้วต้องการ 4 การเคลื่อนที่เพื่อทำให้มันหาร 25 ลงตัว

5071 → 5701 → 7501 → 7510 → 7150

อัลกอริทึม

1. วนลูปผ่านคู่ของตัวเลขทั้งหมดในจำนวน ให้ตัวแรกในคู่อยู่ตำแหน่ง 'i' และตัวที่สองอยู่ตำแหน่ง 'j'
2. วางตัวเลขเหล่านี้ไปที่ตำแหน่งสองตำแหน่งสุดท้ายของจำนวน
3. ถ้าจำนวนมีศูนย์นำหน้า หาตัวเลขที่ไม่ใช่ศูนย์ซ้ายสุดและย้ายไปตำแหน่งแรก
4. ถ้าจำนวนปัจจุบันหาร 25 ลงตัว อัปเดตคำตอบด้วยจำนวนการสลับ

ตัวอย่างโค้ด

#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;

int requiredMoves(long long n) {
    string str = to_string(n);
    int ans = INT_MAX;
    int len = str.size();
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            if (i == j)
                continue;
            string temp = str;
            int cnt = 0;
            for (int k = i; k < len - 1; ++k) {
                swap(temp[k], temp[k + 1]);
                ++cnt;
            }
            for (int k = j - (j > i); k < len - 2; ++k) {
                swap(temp[k], temp[k + 1]);
                ++cnt;
            }
            int pos = -1;
            for (int k = 0; k < len; ++k) {
                if (temp[k] != '0') {
                    pos = k;
                    break;
                }
            }
            for (int k = pos; k > 0; --k) {
                swap(temp[k], temp[k - 1]);
                ++cnt;
            }
            long long num = atoll(temp.c_str());
            if (num % 25 == 0)
                ans = min(ans, cnt);
        }
    }
    if (ans == INT_MAX)
        return -1;
    return ans;
}

int main() {
    int n = 5071;
    cout << "Minimum required moves: " << requiredMoves(n) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum required moves: 4