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.
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
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.
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;
}
You can also try this code with Online C++ Compiler
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);
}
}
You can also try this code with Online Java Compiler
# 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}")
You can also try this code with Online Python Compiler
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."
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.
8+ registered 