Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Constraints
3.
Explanation
4.
Sample Example
4.1.
Input
4.2.
Output
4.3.
Reason
5.
Digit Dynamic Programming
6.
Solution Approach
7.
Algorithm
8.
Implementation
8.1.
Implementation in C++
8.2.
Output
8.3.
Implementation in Java
8.4.
Output
8.5.
Implementation in Python
8.6.
Output
9.
Complexity Analysis
9.1.
Time Complexity
9.2.
Space Complexity
10.
Frequently Asked Questions
10.1.
What is dynamic programming?
10.2.
Where do we use dynamic programming?
10.3.
What do overlapping subproblems mean?
10.4.
What is time complexity?
10.5.
What is space complexity?
11.
Conclusion
Last Updated: Mar 27, 2024
Hard

Classy Numbers

Author Saksham Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Competitive programming is a mental sport that enables you to code a given problem within a specific time limit. One of the common problems you will encounter is the problem of "classy numbers." "Classy numbers" are a unique type of number with specific properties. They cannot have more than three non-zero digits, and no two adjacent digits can be the same. For instance, 102 is a classy number, but 110 is not. In this write-up, we will learn how to count the number of classy numbers in a given range of integers.   

classy numbers

To solve this problem, we will use dynamic programming. By the end of this write-up, you will better understand "classy numbers" and be able to count them in any range of integers.

Problem Statement

We are given a segment [L, R]. "L" and "R" are the given endpoints of a segment. Here, "L" is the left endpoint, and "R" is the right endpoint. We need to find the count of classy numbers present between "L" and "R," inclusive.

Constraints

1 < = L <= R <= 1018

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Explanation

A number is called a “classy number” if its decimal representation contains not more than three non-zero digits.

For instance, 4 is a classy number, while 7281 is not. That is because 4 has only one non-zero digit, but 4321 contains four non-zero digits.

Sample Example

Let us consider an example to understand the question better.

Input

L = 9999 
R= 10001

Output

2

Reason

Numbers in this range are: 9999, 10000, 10001

By the definition of "classy numbers," we can say that there are two classy numbers in this range, i.e., 10000 and 10001.
 

Now this question is a classical question of digit dynamic programming. But what is digit dynamic programming (Digit DP)? Let’s find out.

Digit Dynamic Programming

Digit DP is a dynamic programming technique in which we focus on the digit of a number rather than its actual value. It is a powerful technique that can solve many problems. You may refer to this blog to learn more about digit DP.

The most common digit DP problems require us to count the number of integers in a range that satisfies a particular property. If this property is dependent only on the digit of a number rather than its actual value, we can use the digit DP. 

Now, this is the same case with our problem too. We have been given a range, and based on one property (classy numbers here), we have to find the count of the classy numbers in this range. Thus, we can use digit DP to solve the classy numbers problem as well. Let’s see how.

Solution Approach

We will use the approach that follows to solve this problem.

  • Instead of finding the classy numbers directly from 'L' to 'R,' we will create a function 'COUNT' that will give us classy numbers from 0 to the integer 'N.'
     
  • Once we have the COUNT function, our answer will be COUNT(R) - COUNT(L - 1), as we want to find the count of classy numbers between L and R.
     
  • We will create a ‘DIGIT’ array that stores a given number in an array, building the number from left to right.
     
  • We will then create a 3D DP (dynamic programming) array with three parameters: ‘POS’, ‘CNT’, and ‘FLAG’.
     
  • ‘POS’ signifies the position of the digit we are currently on, ‘CNT’ gives us the number of non-zero digits we have encountered so far, and ‘FLAG’ tells us if the previous digit we used to form our number is equal to the original number or not.
     

Now let's look at the algorithm to code this approach.

Algorithm

The algorithm for the above-discussed approach is as follows:

  • Define a function count(n) that takes an integer n as input and returns the number of classy numbers from 0 to n.
     
  • Convert n to an array of digits using the digit array. To convert a number 'n' to an array of its individual digits, we can use the following steps:
     
  • Initialize an empty array of digits, 'digits_array’'.
     
  • While n is greater than 0, perform the following steps:

    • Let d be the last digit of n (i.e., n % 10).
       
    • Append the value of digit[d] to the 'digits_array' at index 'd'.
       
    • Set n = n / 10.
       
  • Return the 'digits_array'.
     
  • Initialize a 3D DP array, dp[21][21][2] (dp[pos][cnt][flag]), where pos represents the current position in the number, and cnt represents the count of non-zero digits so far. The flag indicates if the previous digit is equal to the corresponding digit in the digit.

    Note: The size of 21 for the dp array was chosen because it may be required to store the maximum number of digits in the input(1018).
     
  • Set the base case for the DP array where dp[0][0][0] is equal to 1. That means we have one possible number, 0, with no non-zero digits.
     
  • Use nested loops to fill the DP array. Iterate through all possible digits for each position starting from the first digit.
     
  • For each digit, calculate the flag's value by checking if the current digit is equal to the corresponding digit in the digit array. If they are equal, set the flag to 1; otherwise, set it to 0.
     
  • Update the DP array using the following relation:

    • dp[pos][cnt][flag]dp[pos - 1][cnt][flag] * 9dp[pos - 1][cnt - 1][1]dp[pos - 1][cnt][0]
       

Where dp[pos - 1][cnt][flag] * 9 represents the number of possible numbers we can form by adding any non-zero digit to the current segment. The "* 9" means we can choose from any digit from 1 to 9, and not 0 unless the cnt is greater than 0.

dp[pos - 1][cnt - 1][1] represents the number of possible numbers we can form by starting a new segment with a non-zero digit. The "1" flag means that we are forming a number that is less than the input number, so we can choose any digit from 1 to 9.
 

dp[pos - 1][cnt][0]  represents the number of possible numbers we can form by starting a new segment with a zero digit. The "0" flag means that we are still forming a number that is greater than the input number, so we can only choose the digit 0 if there is already a non-zero digit in the current segment.
 

  • After filling the DP array, return the total number of classy numbers up to n by summing up the values in the dp[len(digit)][cnt][flag] sub-array for all possible cnt and flag values.
     
  • Finally, to get the count of classy numbers between L and R, we can simply calculate count(R)count(L).
     

Below is the code for the above algorithm in C++, Java, and Python.

Implementation

The implementation in C++ is as follows.

Implementation in C++

#include <iostream>
#include <vector>

using namespace std;

// Function to count classy numbers
long long solve(long long pos, long long cnt, long long flag, vector<long long> &digits, vector<vector<vector<long long>>> &dp) {

    // Memoization condition check
    if (dp[pos][cnt][flag] != -1)
        return dp[pos][cnt][flag];

    // Base case
    if (pos == 20) {
        // It will only be a classy number when 'CNT' <=3.
        if (cnt <= 3) return 1;
        else return 0;
    }

    long long ans = 0;

    // If the 'FLAG' is 0, then the range of the next digit is from '0' to digit[POS]
    long long range = 10;
    
    // exact match 
    if(flag == 0){
        range = digits[pos];

        if(digits[pos] == 0){
            ans += solve(pos + 1, cnt, 0, digits, dp);
        }
        else{
            ans += solve(pos + 1, cnt + 1, 0, digits, dp);
        }
    }

    for (long long d = 0; d < range; d++) {
        if(d!=0){
            ans += solve(pos + 1, cnt + 1, 1, digits, dp);
        }
        else{
            ans += solve(pos + 1, cnt, 1, digits, dp);
        }
    }

    // Store the answer in the 'DP' array and return it
    return dp[pos][cnt][flag] = ans;
}

// Function to initialize tables
long long count(long long n) {
    // Initialising DP array
    vector<vector<vector<long long>>> dp(21, vector<vector<long long>> (21, vector<long long> (2, -1)));

    // Initializing digit array
    vector<long long> digits(21, 0);
    /* 
        The variable c is used to keep 
        track of the position of the current
        digit in the input number. It is
        initialized to 19 because the input 
        number has at most 19 digits, so 
        the maximum position is 18 (since 
        the positions are 0-indexed)
    */
    long long index = 19;

    // Filling the digit array.
    while (n) {
        long long d = n % 10;
        n /= 10;
        digits[index--] = d;
    }
    return solve(0, 0, 0, digits, dp);
}

int main() {
    long long L = 9999, R = 10001;

    long long countL = count(L-1);
    long long countR = count(R);
    long long classy_numbers = countR - countL;
    cout << "The number of classy numbers between " << L << " and " << R << " is " << classy_numbers << endl;

    return 0;
}

Output

output

The implementation in Java is as follows.

Implementation in Java

import java.util.*;

class Main {
    // Function to count classy numbers
    static long solve(long pos, long cnt, long flag,  long[] digits, long[][][] dp) {

        // Memoization condition check
        if (dp[(int) pos][(int) cnt][(int) flag] != -1)
            return dp[(int) pos][(int) cnt][(int) flag];

        // Base case
        if (pos == 20) {

            /*
                It will only be a classy 
                number when 'CNT' <=3
            */
            if (cnt <= 3)
                return 1;
            return 0;
        }
        long ans = 0;

        /*
            If the 'FLAG' is 0, then 
            the range of the next digit 
            is from '0' to digit[POS]
        */
        long range = 10;
    
        // exact match 
        if(flag == 0){
            range = (long) digits[(int) pos];

            if(digits[(int) pos] == 0){
                ans += solve(pos + 1, cnt, 0, digits, dp);
            }
            else{
                ans += solve(pos + 1, cnt + 1, 0, digits, dp);
            }
        }

        for (long d = 0; d < range; d++) {
            if(d!=0){
                ans += solve(pos + 1, cnt + 1, 1, digits, dp);
            }
            else{
                ans += solve(pos + 1, cnt, 1, digits, dp);
            }
        }
        // Store the answer in the 'DP' array and return it
        return dp[(int) pos][(int) cnt][(int) flag] = ans;
    }

    // Function to initialize tables
    static long count(long n) {
        long[][][] dp = new long[21][21][2];
        // Initialising DP array
        for (int i = 0; i < 21; i++) {
            for (int cnt = 0; cnt < 21; cnt++) {
                for (int f = 0; f < 2; f++)
                    dp[i][cnt][f] = -1;
            }
        }
        long[] digits = new long[21];

        long index = 19;

        // Initializing digit array
        for (int i = 0; i <= index; i++) {
            digits[i] = 0;
        }

        // Filling the digit array
        while (n > 0) {
            long d = n % 10;
            n /= 10;
            digits[(int) index--] = d;
        }
        return solve(0, 0, 0, digits, dp);
    }

    public static void main(String[] args) {
        long L = 9999, R = 10001;

        long countL = count(L-1);
        long countR = count(R);
        long classy_numbers = countR - countL;
        System.out.println("The number of classy numbers between " + L + " and " + R + " is " + classy_numbers);
    }
}

Output

output

The implementation in Python is as follows.

Implementation in Python

# Function to count classy numbers
def solve(pos, cnt, flag, digits, dp):

    # Memoization condition check
    if dp[pos][cnt][flag] != -1:
        return dp[pos][cnt][flag]

    # Base case.
    if pos == 20:

        """ 
            It will only be a classy 
            number when 'CNT' <=3
        """
        if cnt <= 3:
            return 1
        return 0

    ans = 0

    """
        If the 'FLAG' is 0, then 
        the range of the next digit
        is from '0' to digit[POS]
    """
    range_ = 10

   #  exact match
    if flag == 0:
        range_ = digits[pos]
        if(digits[pos] == 0):
            ans += solve(pos + 1, cnt, 0, digits, dp)
        else:
            ans += solve(pos + 1, cnt + 1, 0, digits, dp)
        
    for d in range(range_):
         if(d != 0):
            ans += solve(pos + 1, cnt + 1, 1, digits, dp)
         else:
            ans += solve(pos + 1, cnt , 1, digits, dp)

    """
        Store the answer in the 
        'DP' array and return it
    """
    dp[pos][cnt][flag] = ans
    return ans

# Function to initialize tables
def count(n):
    dp = [[[-1 for i in range(2)] for j in range(21)] for k in range(21)]
    # Initialising DP array
    index = 19

    # Initializing digit array
    digits = [0] * 21
    for i in range(index + 1):
        digits[i] = 0

    # Filling the digit array
    while n:
        d = n % 10
        n //= 10
        digits[index] = d
        index -= 1

    return solve(0, 0, 0, digits, dp)

L, R = 9999, 10001

countL = count(L-1)
countR = count(R)
classy_numbers = countR - countL
print(f"The number of classy numbers between {L} and {R} is {classy_numbers}")

Output

output

Let’s now perform a quick complexity analysis on this code.

Complexity Analysis

The space and time complexities of this approach are as follows.

Time Complexity

The time complexity of the given code in terms of the input size n is O(log n * 20 * 21 * 2), which can be simplified as O(log n).

Reason: The time complexity can be analyzed as follows:
 

  • The code iterates over the digits of the input number, which has a maximum of 19 digits.
     
  • For each digit, there are at most 21 possible values for the count and 2 possible values for the flag.
     
  • The solve() function is called recursively for each possible combination of pos, cnt, and flag, with a time complexity of O(21 * 21 * 2) = O(1).
     

Therefore, the total time complexity of the code is dominated by the loop over the input digits, which has a time complexity of O(log n).

Space Complexity

O(1) is the space complexity of this code.

Reason: The space complexity of the code is O(21 * 21 * 2) = O(840), which is constant and does not depend on the size of the input.

Check out this problem - Frog Jump

Check out Longest Common Substring

Frequently Asked Questions

What is dynamic programming?

Dynamic programming is an optimization method used in various programming problems. We use it to memorize the results so that they can be used later when needed.

Where do we use dynamic programming?

Dynamic programming is used in problems where the solution depends on smaller, overlapping subproblems.

What do overlapping subproblems mean?

A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.

What is time complexity?

The amount of time an algorithm or code takes to execute each instruction is known as its time complexity.

What is space complexity?

The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity."

 Also Read - Strong number in c

Conclusion

We saw how we could solve competitive programming questions using digit DP and solved one of the interesting questions, Classy Numbers. We learned about the implementation of its solution in various programming languages. We also discussed the time and space complexity of the solution.

You can follow these links for more such problems.

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning, Ninjas!

Previous article
Nth Number
Next article
Longest Bitonic Subsequence
Live masterclass