การนับตัวเลขในช่วง

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

ดังนั้น หากอินพุตเป็น d =1 ต่ำ =1 สูง =13 เอาต์พุตจะเป็น 6 เนื่องจากตัวเลข d=1 เกิดขึ้น 6 ครั้ง เช่น 1,10,11,12,13

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

กำหนดฟังก์ชันศูนย์ () ซึ่งจะใช้เวลา n

• ret :=0, x :=0

• ถ้า n เท่ากับ 0 แล้ว −

  • กลับ 1

• สำหรับการเริ่มต้น m :=1 เมื่อ m <=n อัปเดต m :=m * 10 ทำ -

  • a :=n / m

  • b :=n mod m

  • z :=mod 10

  • หากจำนวนหลักในหน่วย m เท่ากับจำนวนหลักใน n แล้ว −

    • ออกจากวง

  • ถ้า z> x แล้ว −

    • ret :=ret + ((a / 10) + 1)

  • มิฉะนั้นเมื่อ z เหมือนกับ x แล้ว

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

  • มิฉะนั้น

    • ret :=ret + (a / 10)

• รีเทิร์น

• กำหนดฟังก์ชัน f() ซึ่งจะใช้เวลา x, n,

• ยกเลิก :=0

• สำหรับการเริ่มต้น m :=1 เมื่อ m <=n อัปเดต m :=m * 10 ทำ -

  • a :=n / m

  • b :=n mod m

  • z :=mod 10

  • ถ้า z> x แล้ว

    • ret :=ret + ((a / 10) + 1)

  • มิฉะนั้นเมื่อ z เหมือนกับ x แล้ว −

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

  • มิฉะนั้น

    • ret :=ret + (a / 10)

  • ถ้า x เท่ากับ 0 แล้ว −

    • ret :=ret - ม

• รีเทิร์น

• จากวิธีหลักให้ทำดังนี้

• รีเทิร์น

• ผลตอบแทน f(d, สูง - f(d, ต่ำ - 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;
         }
         cout << ret << endl;
      }
      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);
   }
};
main(){
   Solution ob;
   cout << (ob.digitsCount(1,1,13));
}

อินพุต

1,1,13

ผลลัพธ์

6