CSES Solutions – Counting Numbers
Given two integers a and b. Your task is to count the number of integers between a and b where no two adjacent digits are the same.
Examples:
Input: a=11, b=13
Output: 2
Explanation: The two numbers are 12 and 13.Input: a=123, b=321
Output: 171
Approach:
The idea is to use digit DP to solve this problem. The dp array dp[n][prev_digit][leading_zero][tight] represents count of valid numbers(whose adjacent digits are not same) formed by the n digits.
The parameters can be described as following:
curr
: Represents the current position or digit being processed.prev_digit
: Represents the previous digit at the previous position.leading_zero
: Indicates whether there is a leading zero in the current number (1 if there is a leading zero, 0 otherwise).
tight
: Indicates whether the current number formed so far is tight (1 if tight, 0 otherwise).During the transition, the code iterates through possible digits for the current position, checking their validity by ensuring they differ from the previous digit and, if applicable, allowing consecutive leading zeroes. The state is then updated by recursively calling the
mem
function for the next position, adjusting flags likeleading_zero
andtight
accordingly. The count of valid numbers is accumulated by considering different digit choices, and memoization is applied to optimize repetitive calculations.The final answer will be the difference between count of valid numbers from [0,b] and [0,a-1].
Follow the steps to solve the problem:
- Initialize a dynamic programming table dp[20][10][2][2].
- The
mem
function calculates the count of valid numbers based on the digit DP approach. It takes parameterss
(string representation of the number),curr
(current position),prev_digit
(previous digit),leading_zero
(consecutive leading zeroes), andtight
(tightness of the number). - If
curr
is 0, indicating that the entire number has been processed, the function returns 1. If the result for the current state is already computed, it is directly returned. - The limit for the current position is determined based on whether the number is tight or not. If not tight, the limit is set to 9; otherwise, it is equal to the digit at current position.
- The function iterates through possible digits (from 0 to the determined limit) for the current position. For each digit:
- Check if the current digit is valid, considering constraints:
- If
leading_zero
is 0(means there are no leading zeroes) , the current digit must differ from theprev_digit
.
- If
- Update state parameters (
new_leading_zero
andnew_tight
) based on the current digit. - Recursively calls the
mem
function for the next position (curr - 1
).
- Check if the current digit is valid, considering constraints:
- Calculate the count of valid numbers by summing up the results from different digit choices and update the memoization table with the count of valid numbers for the current state.
- The final answer will count2- count1, where
count1
represents count of valid numbers from [0,a-1] and count2 represents number of valid numbers from [0,b].
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// dp array to memoize results of subproblems
ll dp[20][10][2][2];
// Function to calculate the count of valid numbers using Digit DP
ll mem(string s, ll curr, ll prev_digit, ll leading_zero, ll tight)
{
// Base case: entire number processed
if (curr == 0)
{
return 1;
}
// Check if result for the current state is already computed
if (dp[curr][prev_digit][leading_zero][tight] != -1)
return dp[curr][prev_digit][leading_zero][tight];
// Determine the limit for the current position based on tightness
ll limit;
if (tight == 0)
{
limit = 9;
}
else
{
ll sz = s.size();
limit = s[sz - curr] - 48;
}
ll countNumbers = 0;
// Iterate through possible digits for the current position
for (ll curr_digit = 0; curr_digit <= limit; curr_digit++)
{
// Check validity based on constraints
if (leading_zero == 0 && (curr_digit == prev_digit))
{
continue;
}
// Update state parameters based on the current digit
ll new_leading_zero = (leading_zero == 1 && curr_digit == 0) ? 1 : 0;
ll new_tight = (curr_digit == limit && tight == 1) ? 1 : 0;
// Recursively call the mem function for the next position
countNumbers += mem(s, curr - 1, curr_digit, new_leading_zero, new_tight);
}
// Update the memoization table with the count of valid numbers for the current state
dp[curr][prev_digit][leading_zero][tight] = countNumbers;
return dp[curr][prev_digit][leading_zero][tight];
}
// Driver Code
int main()
{
ll a=123, b=321;
ll count1 = 0;
// Initialize dp table with -1
memset(dp, -1, sizeof(dp));
// Calculate count of valid numbers from [0, a-1]
string str1 = to_string(a - 1);
if (a != 0)
count1 = mem(str1, str1.size(), -1, 1, 1);
// Calculate count of valid numbers from [0, b]
memset(dp, -1, sizeof(dp));
string str2 = to_string(b);
ll count2 = mem(str2, str2.size(), -1, 1, 1);
// Output the difference between count of valid numbers from [0, b] and [0, a-1]
cout << count2 - count1;
}
import java.util.Arrays;
public class Main {
// dp array to memoize results of subproblems
static long[][][][] dp = new long[20][10][2][2];
// Function to calculate the count of valid numbers using Digit DP
static long mem(String s, int curr, int prev_digit, int leading_zero, int tight) {
// Base case: entire number processed
if (curr == 0) {
return 1;
}
// Check if result for the current state is already computed
if (dp[curr][prev_digit][leading_zero][tight] != -1)
return dp[curr][prev_digit][leading_zero][tight];
// Determine the limit for the current position based on tightness
int limit;
if (tight == 0) {
limit = 9;
} else {
int sz = s.length();
limit = s.charAt(sz - curr) - '0';
}
long countNumbers = 0;
// Iterate through possible digits for the current position
for (int curr_digit = 0; curr_digit <= limit; curr_digit++) {
// Check validity based on constraints
if (leading_zero == 0 && (curr_digit == prev_digit)) {
continue;
}
// Update state parameters based on the current digit
int new_leading_zero = (leading_zero == 1 && curr_digit == 0) ? 1 : 0;
int new_tight = (curr_digit == limit && tight == 1) ? 1 : 0;
// Recursively call the mem function for the next position
countNumbers += mem(s, curr - 1, curr_digit, new_leading_zero, new_tight);
}
// Update the memoization table with the count of valid numbers for the current state
dp[curr][prev_digit][leading_zero][tight] = countNumbers;
return dp[curr][prev_digit][leading_zero][tight];
}
public static void main(String[] args) {
long a = 123, b = 321;
long count1 = 0;
// Initialize dp table with -1
for (long[][][] arr3D : dp) {
for (long[][] arr2D : arr3D) {
for (long[] arr1D : arr2D) {
Arrays.fill(arr1D, -1);
}
}
}
// Calculate count of valid numbers from [0, a-1]
String str1 = Long.toString(a - 1);
if (a != 0)
count1 = mem(str1, str1.length(), 0, 1, 1);
// Calculate count of valid numbers from [0, b]
for (long[][][] arr3D : dp) {
for (long[][] arr2D : arr3D) {
for (long[] arr1D : arr2D) {
Arrays.fill(arr1D, -1);
}
}
}
String str2 = Long.toString(b);
long count2 = mem(str2, str2.length(), 0, 1, 1);
// Output the difference between count of valid numbers from [0, b] and [0, a-1]
System.out.println(count2 - count1);
}
}
def mem(s, curr, prev_digit, leading_zero, tight):
# Base case: if current position is 0, return 1
if curr == 0:
return 1
# Check if result for the current state is already computed
if dp[curr][prev_digit][leading_zero][tight] != -1:
return dp[curr][prev_digit][leading_zero][tight]
# Determine the limit for the current position based on tightness
limit = 9 if tight == 0 else int(s[len(s) - curr])
count_numbers = 0
# Iterate through possible digits for the current position
for curr_digit in range(limit + 1):
# Check validity based on constraints
if leading_zero == 0 and curr_digit == prev_digit:
continue
# Update state parameters based on the current digit
new_leading_zero = 1 if leading_zero == 1 and curr_digit == 0 else 0
new_tight = 1 if curr_digit == limit and tight == 1 else 0
# Recursively call the mem function for the next position
count_numbers += mem(s, curr - 1, curr_digit, new_leading_zero, new_tight)
# Update the memoization table with the count of valid numbers
# for the current state
dp[curr][prev_digit][leading_zero][tight] = count_numbers
return count_numbers
# Define input values
a, b = 123, 321
count1 = 0
# Initialize dp table with -1
dp = [[[[ -1 for _ in range(2)] for _ in range(2)] for _ in range(10)] for _ in range(20)]
# Calculate count of valid numbers from [0, a-1]
str1 = str(a - 1)
if a != 0:
count1 = mem(str1, len(str1), -1, 1, 1)
# Reset dp table with -1
dp = [[[[ -1 for _ in range(2)] for _ in range(2)] for _ in range(10)] for _ in range(20)]
# Calculate count of valid numbers from [0, b]
str2 = str(b)
count2 = mem(str2, len(str2), -1, 1, 1)
# Output the difference between count of valid numbers from [0, b] and [0, a-1]
print(count2 - count1)
function GFG(s, curr, prev_digit, leading_zero, tight) {
// Base case: entire number processed
if (curr === 0) {
return 1;
}
// Determine the limit for current position based on tightness
let limit = (tight === 0) ? 9 : parseInt(s[s.length - curr]);
let countNumbers = 0;
// Iterate through possible digits for current position
for (let curr_digit = 0; curr_digit <= limit; curr_digit++) {
if (leading_zero === 0 && (curr_digit === prev_digit)) {
continue;
}
let new_leading_zero = (leading_zero === 1 && curr_digit === 0) ? 1 : 0;
let new_tight = (curr_digit === limit && tight === 1) ? 1 : 0;
// Recursively call the mem function for the next position
countNumbers += GFG(s, curr - 1, curr_digit, new_leading_zero, new_tight);
}
return countNumbers;
}
// Driver Code
function main() {
let a = 123, b = 321;
let count1 = 0;
let str1 = (a - 1).toString();
if (a !== 0) {
count1 = GFG(str1, str1.length, -1, 1, 1);
}
// Calculate count of valid numbers from [0, b]
let str2 = b.toString();
let count2 = GFG(str2, str2.length, -1, 1, 1);
// Output the difference between count of the valid numbers from [0, b] and [0, a-1]
console.log(count2 - count1);
}
main();
Output
171
Time Complexity: O(n*100), where n is number of digits of number n.
Auxilary Space: O(n*100)
Contact Us