3519. Count Numbers with Non-Decreasing Digits LeetCode Solution

Last updated: April 22, 2025

In this guide, you will get 3519. Count Numbers with Non-Decreasing Digits LeetCode Solution with the best time and space complexity. The solution to Count Numbers with Non-Decreasing Digits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Numbers with Non-Decreasing Digits solution in C++
Count Numbers with Non-Decreasing Digits solution in Java
Count Numbers with Non-Decreasing Digits solution in Python
Additional Resources

3519. Count Numbers with Non-Decreasing Digits LeetCode Solution image

Problem Statement of Count Numbers with Non-Decreasing Digits

You are given two integers, l and r, represented as strings, and an integer b. Return the count of integers in the inclusive range [l, r] whose digits are in non-decreasing order when represented in base b.
An integer is considered to have non-decreasing digits if, when read from left to right (from the most significant digit to the least significant digit), each digit is greater than or equal to the previous one.
Since the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: l = “23”, r = “28”, b = 8
Output: 3
Explanation:

The numbers from 23 to 28 in base 8 are: 27, 30, 31, 32, 33, and 34.
Out of these, 27, 33, and 34 have non-decreasing digits. Hence, the output is 3.

Example 2:

Input: l = “2”, r = “7”, b = 2
Output: 2
Explanation:

The numbers from 2 to 7 in base 2 are: 10, 11, 100, 101, 110, and 111.
Out of these, 11 and 111 have non-decreasing digits. Hence, the output is 2.

Constraints:

1 <= l.length <= r.length <= 100
2 <= b <= 10
l and r consist only of digits.
The value represented by l is less than or equal to the value represented by r.
l and r do not contain leading zeros.

Complexity Analysis

Time Complexity: O(n \cdot b^2 + n^3)
Space Complexity: O(n \cdot b^2)

3519. Count Numbers with Non-Decreasing Digits LeetCode Solution in C++

class Solution {
 public:
  int countNumbers(const string& l, const string& r, const int b) {
    const vector<int> rDigits = convertToBaseB(r, b);
    vector<int> lDigits = convertToBaseB(l, b);
    vector<int> lMinus1Digits = convertToBaseB(decrement(l), b);
    padToSameLength(lDigits, rDigits);
    padToSameLength(lMinus1Digits, rDigits);
    return (countWithMem(rDigits, b) - countWithMem(lMinus1Digits, b) + kMod) %
           kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  void padToSameLength(vector<int>& a, const vector<int>& b) {
    a.insert(a.begin(), b.size() - a.size(), 0);
  }

  int countWithMem(const vector<int>& digits, const int b) {
    vector<vector<vector<int>>> mem(digits.size(),
                                    vector<vector<int>>(2, vector<int>(b, -1)));
    return count(digits, 0, 0, true, b, mem);
  }

  int count(const vector<int>& num, int pos, int lastDigit, bool tight, int b,
            vector<vector<vector<int>>>& mem) {
    if (pos == num.size())
      return 1;

    if (mem[pos][tight][lastDigit] != -1)
      return mem[pos][tight][lastDigit];

    int res = 0;
    const int limit = tight ? num[pos] : b - 1;

    for (int d = lastDigit; d <= limit; d++) {
      const bool newTight = tight && (d == limit);
      res = (res + count(num, pos + 1, d, newTight, b, mem)) % kMod;
    }

    return mem[pos][tight][lastDigit] = res;
  }

  string decrement(string s) {
    for (int i = s.length() - 1; i >= 0; --i) {
      if (s[i] > '0') {
        --s[i];
        break;
      } else {
        s[i] = '9';
      }
    }
    return s[0] == '0' && s.length() > 1 ? s.substr(1) : s;
  }

  vector<int> convertToBaseB(const string& numStr, const int b) {
    vector<int> digits;
    vector<int> currentNum(1, 0);

    for (const char c : numStr) {
      const int d = c - '0';

      int carry = 0;
      for (int i = 0; i < currentNum.size(); ++i) {
        const long long product = (long long)currentNum[i] * 10 + carry;
        currentNum[i] = product % b;
        carry = product / b;
      }

      while (carry > 0) {
        currentNum.push_back(carry % b);
        carry /= b;
      }

      carry = d;
      for (int i = 0; i < currentNum.size() && carry; ++i) {
        const int sum = currentNum[i] + carry;
        currentNum[i] = sum % b;
        carry = sum / b;
      }

      while (carry > 0) {
        currentNum.push_back(carry % b);
        carry /= b;
      }
    }

    for (int i = currentNum.size() - 1; i >= 0; --i)
      digits.push_back(currentNum[i]);

    if (digits.empty())
      digits.push_back(0);

    return digits;
  }
};
/* code provided by PROGIEZ */

3519. Count Numbers with Non-Decreasing Digits LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3519. Count Numbers with Non-Decreasing Digits LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents