Digit Count in Range (นับจำนวนหลักในช่วง) ใน C++

สมมติว่าเรามีจำนวนเต็ม d ระหว่าง 0 ถึง 9 เรายังมีจำนวนเต็มบวกสองจำนวน low และ high เป็นขอบเขตล่างและบนตามลำดับ เราต้องหาจำนวนครั้งที่ d ปรากฏเป็นหลักเลขในจำนวนเต็มทั้งหมดระหว่าง low และ high รวมถึงขอบเขต low และ high

ดังนั้น หากอินพุทคือ d = 1, low = 1, high = 13 ผลลัพธ์จะเป็น 6 เนื่องจากหลักเลข d=1 ปรากฏ 6 ครั้ง คือ 1, 10, 11, 12, 13

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• กำหนดฟังก์ชัน zero() รับ n

  • ret := 0, x := 0

  • ถ้า n == 0: คืนค่า 1

  • for m := 1; m <= n; m *= 10:

    • a := n / m, b := n % m, z := a % 10

    • ถ้าจำนวนหลักของ m == จำนวนหลักของ n: break

    • ถ้า z > x: ret += ((a/10)+1) * m

    • else if z == x: ret += (a/10) * m + (b+1)

    • else: ret += (a/10) * m

  • คืนค่า ret

• กำหนดฟังก์ชัน f() รับ x, n

  • ret := 0

  • for m := 1; m <= n; m *= 10:

    • a := n / m, b := n % m, z := a % 10

    • ถ้า z > x: ret += ((a/10)+1) * m

    • else if z == x: ret += (a/10) * m + (b+1)

    • else: ret += (a/10) * m

    • ถ้า x == 0: ret -= m

  • คืนค่า ret

• จาก main method: คืนค่า f(d, high) - f(d, low - 1)

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

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

class Solution {
public:
    int digitCount(int x) {
        int ret = 0;
        while (x) {
            ret++;
            x /= 10;
        }
        return ret;
    }

    int zero(int n) {
        int ret = 0;
        int x = 0;
        if (n == 0) return 1;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m;
            int b = n % m;
            int z = a % 10;
            if (digitCount(m) == digitCount(n)) break;
            if (z > x) {
                ret += ((a / 10) + 1) * m;
            } else if (z == x) {
                ret += (a / 10) * m + (b + 1);
            } else {
                ret += (a / 10) * m;
            }
        }
        return ret;
    }

    int f(int x, int n) {
        int ret = 0;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m;
            int b = n % m;
            int z = a % 10;
            if (z > x) {
                ret += ((a / 10) + 1) * m;
            } else if (z == x) {
                ret += (a / 10) * m + (b + 1);
            } else {
                ret += (a / 10) * m;
            }
            if (x == 0) {
                ret -= m;
            }
        }
        return ret;
    }

    int digitsCount(int d, int low, int high) {
        return f(d, high) - f(d, low - 1);
    }
};

int main() {
    Solution ob;
    cout << (ob.digitsCount(1, 1, 13));
    return 0;
}

อินพุต

1, 1, 13

เอาต์พุต

6