Counting Numbers Of N Digits That Are Monotone In C++

Introduction

Monotonic numbers hold significance in both number theory and combinatorics due to their unique properties. These numbers are characterized by having digits arranged in either non-decreasing or non-increasing sequences, showcasing a specific form of symmetry. The focus of this tutorial is to develop a C++ program dedicated to calculating the count of n-digit monotonic numbers. The content will delve into a comprehensive breakdown of the process, offering a meticulous guide to the underlying logic, the approach strategy, and the practical execution of the solution.

Problem Statement:

For a specific value of n, determine the total count of n-digit numbers that exhibit monotonic behavior. For instance:

• ✅ A sequence like 123 is classified as an ascending monotonic number
• ✅ Conversely, a number like 432 is monotonic, but in a descending manner.

We need to determine the total count of numbers that belong to the monotonic classification based on an integer n.

Leading zeros must be avoided in the context of ### Constraints:. Make sure not to include them.

Approach

The considerations we will undertake include combinatorics and dynamic programming. Below is a brief outline of our approach:

• ✅ Non-Decreasing Numbers: A distribution of n digits across 10 digits (the digits 0 to 9) can be done, which gives rise to a non-decreasing number. A combinatorics problem of the type “N ways to place n identical items into r distinct groups” is given by the formula C(n+r−1,r−1), and in this case, it is also applicable.
• ✅ Non-Increasing Numbers: The equation that was derived above can still be employed to calculate non-increasing numbers.
• ✅ Avoid Double Counting: A number such as 111 will be classified as non-decreasing as well as non-increasing. In order to resolve this problem, we take away from the total value of 999 because n digits comprising n times any number between a and 9 are repeated once.
• ✅ Implementation in C++: First, compute combinations from factorials. Non-decreasing and non-increasing digits are solved, whereby loops or functions are used to sum the counts obtained.
• ✅ A distribution of n digits across 10 digits (the digits 0 to 9) can be done, which gives rise to a non-decreasing number.
• ✅ A combinatorics problem of the type “N ways to place n identical items into r distinct groups” is given by the formula C(n+r−1,r−1), and in this case, it is also applicable.
• ✅ The equation that was derived above can still be employed to calculate non-increasing numbers.
• ✅ A number such as 111 will be classified as non-decreasing as well as non-increasing. In order to resolve this problem, we take away from the total value of 999 because n digits comprising n times any number between a and 9 are repeated once.
• ✅ First, compute combinations from factorials.
• ✅ Non-decreasing and non-increasing digits are solved, whereby loops or functions are used to sum the counts obtained.

Example 1:

Let's consider a C++ program for determining monotone numbers with n digits:

#include <iostream>
#include <vector>
using namespace std;

// Function to calculate factorial
long long factorial(int n) {
    if (n == 0 || n == 1) return 1;
    long long result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// Function to calculate combinations: C(n, r) = n! / (r! * (n-r)!)
long long combinations(int n, int r) {
    if (r > n) return 0;
    return factorial(n) / (factorial(r) * factorial(n - r));
}

// Function to count n-digit monotone numbers
long long countMonotoneNumbers(int n) {
    if (n == 0) return 0;

    // Non-decreasing numbers
    long long nonDecreasing = combinations(n + 9, 9);

    // Non-increasing numbers
    long long nonIncreasing = combinations(n + 9, 9);

    // Subtract overcounted numbers (all digits same, 1 through 9)
    long long overlap = 9;

    // Total monotone numbers
    return nonDecreasing + nonIncreasing - overlap;
}

int main() {
    int n;
    cout << "Enter the number of digits (n): ";
    cin >> n;

    cout << "The number of " << n << "-digit monotone numbers is: " 
         << countMonotoneNumbers(n) << endl;

    return 0;
}

Output:

Enter the number of digits (n): 3
The number of 3-digit monotone numbers is: 474

Explanation of Code

• ✅ Factorial Calculation: The factorial function will be used to calculate the volume of n! that corresponds to the combinations formula.
• ✅ Combination Calculation: C(n,r) is computed using the efficient combinations function, which gets the value of C(n, r) but potentially involves the use of many factorials.
• ✅ Main Function: CountMonotoneNumbers: A function that estimates the number of increasing and decreasing digits C(n, r) is calculated, but the overlap, such as the number 111, is accounted for and subtracted, so wards double counting.
• ✅ Input/Output The program receives n as an input, which counts the number of monotone numbers of a certain number of digits which are n.
• ✅ CountMonotoneNumbers: A function that estimates the number of increasing and decreasing digits
• ✅ C(n, r) is calculated, but the overlap, such as the number 111, is accounted for and subtracted, so wards double counting.
• ✅ The program receives n as an input, which counts the number of monotone numbers of a certain number of digits which are n.

Complexity Analysis:

• ✅ Time Complexity: O(n) for factorial computation.
• ✅ Space Complexity: The overall space complexity of the program is O(1).

Example 2:

Let's consider another example to demonstrate the calculation of the quantity of n-digit monotone numbers in C++.

#include <iostream>
#include <vector>
using namespace std;

// Function to count monotone numbers of n digits using dynamic programming
long long countMonotoneNumbers(int n) {
    if (n == 0) return 0;

    // DP table for counting non-decreasing numbers
    vector<vector<long long>> dpIncreasing(n + 1, vector<long long>(10, 0));

    // DP table for counting non-increasing numbers
    vector<vector<long long>> dpDecreasing(n + 1, vector<long long>(10, 0));

    // Base case: For 1-digit numbers
    for (int digit = 1; digit <= 9; ++digit) {
        dpIncreasing[1][digit] = 1;
        dpDecreasing[1][digit] = 1;
    }

    // Fill DP tables for numbers with more than 1 digit
    for (int length = 2; length <= n; ++length) {
        for (int digit = 1; digit <= 9; ++digit) {
            // Non-decreasing: Sum of all digits <= current digit
            dpIncreasing[length][digit] = dpIncreasing[length][digit - 1] + dpIncreasing[length - 1][digit];
            // Non-increasing: Sum of all digits >= current digit
            dpDecreasing[length][digit] = dpDecreasing[length][digit - 1] + dpDecreasing[length - 1][digit];
        }
    }

    // Calculate total non-decreasing and non-increasing numbers
    long long nonDecreasing = 0, nonIncreasing = 0;
    for (int digit = 1; digit <= 9; ++digit) {
        nonDecreasing += dpIncreasing[n][digit];
        nonIncreasing += dpDecreasing[n][digit];
    }

    // Subtract overlap (numbers where all digits are the same)
    long long overlap = 9; // 1 digit repeated n times, for each digit 1-9

    return nonDecreasing + nonIncreasing - overlap;
}

int main() {
    int n;
    cout << "Enter the number of digits (n): ";
    cin >> n;

    long long result = countMonotoneNumbers(n);
    cout << "The number of " << n << "-digit monotone numbers is: " << result << endl;

    return 0;
}

Output:

Enter the number of digits (n): 10
The number of 10-digit monotone numbers is: 87507

Explanation:

• ✅ Dynamic Programming Tables dpIncreasinglength: It stores the count of lengthlengthlength-digit non-decreasing numbers ending with the digit digit. dpDecreasinglength: It stores the count of lengthlengthlength-digit non-increasing numbers starting with the digit digit.
• ✅ Initialization For length=1, each digit from 1 to 9 contributes exactly one number to both tables.
• ✅ Transition Formula Non-Decreasing:
• ✅ dpIncreasinglength: It stores the count of lengthlengthlength-digit non-decreasing numbers ending with the digit digit.
• ✅ dpDecreasinglength: It stores the count of lengthlengthlength-digit non-increasing numbers starting with the digit digit.
• ✅ For length=1, each digit from 1 to 9 contributes exactly one number to both tables.
• ✅ Non-Decreasing:

dpIncreasing[length][digit]=dpIncreasing[length][digit−1]+dpIncreasing[length−1][digit]

It calculates the total of numbers that end with digits that are less than or equal to a specified digit.

• ✅ Decreasing:

dpDecreasing[length][digit]=dpDecreasing[length][digit−1]+dpDecreasing[length−1][digit]

It calculates the total of numbers that begin with digits equal to or greater than a specified digit.

1. Dealing with Overlapping Ranges

• ✅ Adjust by subtracting 999 from the outcome to accommodate numbers with repeated identical digits.

Complexity Analysis:

• ✅ Time Complexity: O(n.9) Filling the DP table involves iterating over n lengths and 9 digits per length.
• ✅ Space Complexity: O(n.9) Two DP tables are used for storing intermediate results.

Example 3:

Let's consider another example to demonstrate how to calculate the quantity of n-digit monotone numbers in C++.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Define a type for the memoization key
using Key = pair<int, int>; // <remaining_digits, previous_digit>

// Hash function for pair (to use it in unordered_map)
struct KeyHash {
    size_t operator()(const Key &key) const {
        return hash<int>()(key.first) ^ hash<int>()(key.second);
    }
};

// Recursive function to count monotone numbers
long long countMonotoneHelper(int remaining_digits, int previous_digit, unordered_map<Key, long long, KeyHash> &memo, bool isIncreasing) {
    // Base case: No more digits to add
    if (remaining_digits == 0) return 1;

    // Check if the result is already computed
    Key key = {remaining_digits, previous_digit};
    if (memo.find(key) != memo.end()) return memo[key];

    long long count = 0;

    if (isIncreasing) {
        // Count non-decreasing numbers
        for (int digit = previous_digit; digit <= 9; ++digit) {
            count += countMonotoneHelper(remaining_digits - 1, digit, memo, true);
        }
    } else {
        // Count non-increasing numbers
        for (int digit = previous_digit; digit >= 1; --digit) {
            count += countMonotoneHelper(remaining_digits - 1, digit, memo, false);
        }
    }

    // Store the result in the memo table
    memo[key] = count;
    return count;
}

// Wrapper function to calculate total monotone numbers
long long countMonotoneNumbers(int n) {
    if (n == 0) return 0;

    unordered_map<Key, long long, KeyHash> memoIncreasing; // Memoization for increasing numbers
    unordered_map<Key, long long, KeyHash> memoDecreasing; // Memoization for decreasing numbers

    long long nonDecreasing = 0, nonIncreasing = 0;

    // Calculate non-decreasing numbers
    for (int digit = 1; digit <= 9; ++digit) {
        nonDecreasing += countMonotoneHelper(n - 1, digit, memoIncreasing, true);
    }

    // Calculate non-increasing numbers
    for (int digit = 9; digit >= 1; --digit) {
        nonIncreasing += countMonotoneHelper(n - 1, digit, memoDecreasing, false);
    }

    // Subtract overlap (numbers where all digits are the same)
    long long overlap = 9; // 1 digit repeated n times for each digit 1-9

    return nonDecreasing + nonIncreasing - overlap;
}

int main() {
    int n;
    cout << "Enter the number of digits (n): ";
    cin >> n;

    long long result = countMonotoneNumbers(n);
    cout << "The number of " << n << "-digit monotone numbers is: " << result << endl;

    return 0;
}

Output:

Enter the number of digits (n): 10
The number of 10-digit monotone numbers is: 87507

Explanation of the Code:

• ✅ Recursive Function Logic The function countMonotoneHelper recursively computes the count of monotone numbers for a given number of remainingdigits and a previousdigit. It uses two cases: Non-decreasing: The current digit must be ≥\geq≥ previousdigit. Non-increasing: The current digit must be ≤\leq≤ previousdigit.
• ✅ Memoization In order to avoid recomputation, the results of intermediate states (defined by remainingdigits and previousdigit) are stored in an unordered_map using the Key type. It ensures that we compute each unique state exactly once.
• ✅ Overlap Handling Like other methods, numbers where all digits are the same (e.g., 111 or 222) are counted in both increasing and decreasing categories, so we subtract the overlap.
• ✅ The function countMonotoneHelper recursively computes the count of monotone numbers for a given number of remainingdigits and a previousdigit.
• ✅ It uses two cases: Non-decreasing: The current digit must be ≥\geq≥ previousdigit. Non-increasing: The current digit must be ≤\leq≤ previousdigit.
• ✅ Non-decreasing: The current digit must be ≥\geq≥ previous_digit.
• ✅ Non-increasing: The current digit must be ≤\leq≤ previous_digit.
• ✅ In order to avoid recomputation, the results of intermediate states (defined by remainingdigits and previousdigit) are stored in an unordered_map using the Key type.
• ✅ It ensures that we compute each unique state exactly once.
• ✅ Like other methods, numbers where all digits are the same (e.g., 111 or 222) are counted in both increasing and decreasing categories, so we subtract the overlap.

Complexity Analysis:

• ✅ Time Complexity: O(n×9^2) For each digit, the recursive function considers up to 9 choices for the next digit. With memoization, redundant computations are avoided.
• ✅ Space Complexity: O(n×9) The space is used for the memoization table and the recursion stack.
• ✅ For each digit, the recursive function considers up to 9 choices for the next digit. With memoization, redundant computations are avoided.
• ✅ The space is used for the memoization table and the recursion stack.

Advantages of Solving Monotone Counting Problems:

Several advantages of Monotone Counting Problems in C++ are as follows:

• ✅ Increases Intelligence in Algorithms: Monotone counting problems integrate ideas from combinatorics and dynamic programming, as well as recursion. They are useful for learning more about problem solving and algorithms in general.
• ✅ Invention of New More Efficient Solutions: Learning how to create algorithms with different techniques, such as DP or recursion with memoization, will optimize the slower and inefficient algorithms for both time and space.
• ✅ Skill Fund for Competitive Programming: Difficult sets of problems are found in competitive programming contests. Writing solutions for them makes the contestants ready for those types of problems.
• ✅ Careful of Scalability: When we meet limits like factorial overflow or high space complexity set, we learn that algorithms must be scalable, which is an important lesson in software engineering.

Applications of Monotone Numbers:

Several applications of Monotone Numbers in C++ are as follows:

• ✅ Validation of Data in Database Systems: Monotone sequences are often used to represent ordered data, such as stock prices or temperatures recorded per unit of time. Finding or counting there is common monotonicity will ensure the data is correct.
• ✅ Secret Writing in Computers: Constructing or analyzing monotone numbers could be useful in cryptographic algorithms for building ordered keys or other sequences that recognize order.
• ✅ Recognition Pattern in AI/ML: Proposing a number of these characteristics is important for building machine learning models when it comes to identifying the existence of continuous increasing or decreasing trends in time-series data, such as using stock market data for analysis or forecasting the weather.
• ✅ Sorting Algorithms: Also, monotonic sequences can optimize sorting algorithms or lessen the number of sorting operations needed.
• ✅ Optimization Problems: Monotonicity is a typical constraint in optimization problems like assigning resources or sequencing the tasks to be done.
• ✅ Combinatorics for Practical Application: For instance, the problem is similar to putting n identical elements into r bins (digits), which is useful in inventory control and logistics problems.

Future Extensions:

• ✅ Handling Leading Zeros: Widen the concepts to manage allowing leading zeros when needed, like in binary or specific systems of numeration.
• ✅ Variable Radix Systems: Change the logic for other bases, such as base 16 for hexadecimal or base 8 for octal.
• ✅ Visual Representation: Add visual representation for the solution of the problem by drawing the DP table or the recursion tree to facilitate understanding the solution.
• ✅ Performance Benchmarking: In order to demonstrate the merits and demerits, it is worthwhile to report the run time of all three methods and their memory usage against a range of n values to see if there are any differences.

Conclusion:

In summary, analyzing the quantity of n variables that constitute a monotonic number with n digits presents an intriguing challenge as it showcases the application of combinatorial principles and algorithmic ideas. Within the C++ assignment, we're essentially simplifying the task to focus on the category of sequences that are either non-decreasing or non-increasing.