หา N % 4 ของตัวเลขขนาดใหญ่ด้วย C++

ภาพรวมปัญหา

ได้รับตัวเลขขนาดใหญ่เป็นสตริง หาเศษเมื่อหารด้วย 4

ตัวอย่าง

อินพุต

num = "453425245"

เอาต์พุต

1

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

คุณสมบัติ: เศษของการหาร 4 ขึ้นอยู่กับ 2 หลักสุดท้ายเท่านั้น

เพราะ 100 หาร 4 ลงตัว → หลักร้อยขึ้นไปไม่ส่งผลต่อเศษ

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

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

int calc4Mod(string num, int len) {
    int rem;
    if (len == 1)
        rem = num[0] - '0';
    else
        rem = (num[len - 2] - '0') * 10 + (num[len - 1] - '0');
    return rem % 4;
}

int main() {
    string num = "84525765476513";
    int len = num.length();
    cout << "The remainder of the number with 4 is " << calc4Mod(num, len);
    return 0;
}

เอาต์พุต

The remainder of the number with 4 is 1

สรุป

O(1) time complexity ใช้ได้กับตัวเลขใหญ่มากที่เก็บใน string