Given a range [L, R], the task is to find the count of numbers from this range that satisfy the below conditions:
- All the digit in the number are distinct.
- All the digits are less than or equal to 5.
Examples:
Input: L = 4, R = 13
Output: 5
4, 5, 10, 12 and 13 are the only
valid numbers in the range [4, 13].Input: L = 100, R = 1000
Output: 100
Approach: The question seems simple if the range is small because in that case, all the numbers from the range can be iterated and checked whether they are valid or not. But since the range could be large, it can be observed all the digits of a valid number has to be distinct and from the range [0, 5] which suggests that the maximum number cannot exceed 543210.
Now instead of checking for every number, the next valid number in the series can be generated from the previously generated numbers. The idea is similar to the approach discussed here.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Maximum possible valid number#define MAX 543210// To store all the required number// from the range [1, MAX]vector<string> ans;// Function that returns true if x// satisfies the given conditionsbool isValidNum(string x){ // To store the digits of x map<int, int> mp; for (int i = 0; i < x.length(); i++) { // If current digit appears more than once if (mp.find(x[i] - '0') != mp.end()) { return false; } // If current digit is greater than 5 else if (x[i] - '0' > 5) { return false; } // Put the digit in the map else { mp[x[i] - '0'] = 1; } } return true;}// Function to generate all the required// numbers in the range [1, MAX]void generate(){ // Insert first 5 valid numbers queue<string> q; q.push("1"); q.push("2"); q.push("3"); q.push("4"); q.push("5"); bool flag = true; // Inserting 0 externally because 0 cannot // be the leading digit in any number ans.push_back("0"); while (!q.empty()) { string x = q.front(); q.pop(); // If x satisfies the given conditions if (isValidNum(x)) { ans.push_back(x); } // Cannot append anymore digit as // adding a digit will repeat one of // the already present digits if (x.length() == 6) continue; // Append all the valid digits one by // one and push the new generated // number to the queue for (int i = 0; i <= 5; i++) { string z = to_string(i); // Append the digit string temp = x + z; // Push the newly generated // number to the queue q.push(temp); } }}// Function to compare two strings// which represent a numerical valuebool comp(string a, string b){ if (a.size() == b.size()) return a < b; else return a.size() < b.size();}// Function to return the count of// valid numbers in the range [l, r]int findcount(string l, string r){ // Generate all the valid numbers // in the range [1, MAX] generate(); // To store the count of numbers // in the range [l, r] int count = 0; // For every valid number in // the range [1, MAX] for (int i = 0; i < ans.size(); i++) { string a = ans[i]; // If current number is within // the required range if (comp(l, a) && comp(a, r)) { count++; } // If number is equal to either l or r else if (a == l || a == r) { count++; } } return count;}// Driver codeint main(){ string l = "1", r = "1000"; cout << findcount(l, r); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Maximum possible valid numberstatic int MAX = 543210;// To store all the required number// from the range [1, MAX]static Vector<String> ans = new Vector<String>();// Function that returns true if x// satisfies the given conditionsstatic boolean isValidNum(String x){ // To store the digits of x HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int i = 0; i < x.length(); i++) { // If current digit appears more than once if (mp.containsKey(x.charAt(i) - '0')) { return false; } // If current digit is greater than 5 else if (x.charAt(i) - '0' > 5) { return false; } // Put the digit in the map else { mp.put(x.charAt(i) - '0', 1); } } return true;}// Function to generate all the required// numbers in the range [1, MAX]static void generate(){ // Insert first 5 valid numbers Queue<String> q = new LinkedList<String>(); q.add("1"); q.add("2"); q.add("3"); q.add("4"); q.add("5"); boolean flag = true; // Inserting 0 externally because 0 cannot // be the leading digit in any number ans.add("0"); while (!q.isEmpty()) { String x = q.peek(); q.remove(); // If x satisfies the given conditions if (isValidNum(x)) { ans.add(x); } // Cannot append anymore digit as // adding a digit will repeat one of // the already present digits if (x.length() == 6) continue; // Append all the valid digits one by // one and push the new generated // number to the queue for (int i = 0; i <= 5; i++) { String z = String.valueOf(i); // Append the digit String temp = x + z; // Push the newly generated // number to the queue q.add(temp); } }}// Function to compare two Strings// which represent a numerical valuestatic boolean comp(String a, String b){ if (a.length()== b.length()) { int i = a.compareTo(b); return i < 0 ? true : false; } else return a.length() < b.length();}// Function to return the count of// valid numbers in the range [l, r]static int findcount(String l, String r){ // Generate all the valid numbers // in the range [1, MAX] generate(); // To store the count of numbers // in the range [l, r] int count = 0; // For every valid number in // the range [1, MAX] for (int i = 0; i < ans.size(); i++) { String a = ans.get(i); // If current number is within // the required range if (comp(l, a) && comp(a, r)) { count++; } // If number is equal to either l or r else if (a == l || a == r) { count++; } } return count;}// Driver codepublic static void main (String[] args){ String l = "1", r = "1000"; System.out.println(findcount(l, r));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approachfrom collections import deque# Maximum possible valid numberMAX = 543210# To store all the required number# from the range [1, MAX]ans = []# Function that returns true if x# satisfies the given conditionsdef isValidNum(x): # To store the digits of x mp = dict() for i in range(len(x)): # If current digit appears more than once if (ord(x[i]) - ord('0') in mp.keys()): return False # If current digit is greater than 5 elif (ord(x[i]) - ord('0') > 5): return False # Put the digit in the map else: mp[ord(x[i]) - ord('0')] = 1 return True# Function to generate all the required# numbers in the range [1, MAX]def generate(): # Insert first 5 valid numbers q = deque() q.append("1") q.append("2") q.append("3") q.append("4") q.append("5") flag = True # Inserting 0 externally because 0 cannot # be the leading digit in any number ans.append("0") while (len(q) > 0): x = q.popleft() # If x satisfies the given conditions if (isValidNum(x)): ans.append(x) # Cannot append anymore digit as # adding a digit will repeat one of # the already present digits if (len(x) == 6): continue # Append all the valid digits one by # one and append the new generated # number to the queue for i in range(6): z = str(i) # Append the digit temp = x + z # Push the newly generated # number to the queue q.append(temp)# Function to compare two strings# which represent a numerical valuedef comp(a, b): if (len(a) == len(b)): if a < b: return True else: return len(a) < len(b)# Function to return the count of# valid numbers in the range [l, r]def findcount(l, r): # Generate all the valid numbers # in the range [1, MAX] generate() # To store the count of numbers # in the range [l, r] count = 0 # For every valid number in # the range [1, MAX] for i in range(len(ans)): a = ans[i] # If current number is within # the required range if (comp(l, a) and comp(a, r)): count += 1 # If number is equal to either l or r elif (a == l or a == r): count += 1 return count# Driver codel = "1"r = "1000"print(findcount(l, r))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System;using System.Collections.Generic; class GFG{// Maximum possible valid numberstatic int MAX = 543210;// To store all the required number// from the range [1, MAX]static List<String> ans = new List<String>();// Function that returns true if x// satisfies the given conditionsstatic bool isValidNum(String x){ // To store the digits of x Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < x.Length; i++) { // If current digit appears more than once if (mp.ContainsKey(x[i] - '0')) { return false; } // If current digit is greater than 5 else if (x[i] - '0' > 5) { return false; } // Put the digit in the map else { mp.Add(x[i] - '0', 1); } } return true;}// Function to generate all the required// numbers in the range [1, MAX]static void generate(){ // Insert first 5 valid numbers Queue<String> q = new Queue<String>(); q.Enqueue("1"); q.Enqueue("2"); q.Enqueue("3"); q.Enqueue("4"); q.Enqueue("5"); bool flag = true; // Inserting 0 externally because 0 cannot // be the leading digit in any number ans.Add("0"); while (q.Count!=0) { String x = q.Peek(); q.Dequeue(); // If x satisfies the given conditions if (isValidNum(x)) { ans.Add(x); } // Cannot append anymore digit as // adding a digit will repeat one of // the already present digits if (x.Length == 6) continue; // Append all the valid digits one by // one and push the new generated // number to the queue for (int i = 0; i <= 5; i++) { String z = i.ToString(); // Append the digit String temp = x + z; // Push the newly generated // number to the queue q.Enqueue(temp); } }}// Function to compare two Strings// which represent a numerical valuestatic bool comp(String a, String b){ if (a.Length == b.Length) { int i = a.CompareTo(b); return i < 0 ? true : false; } else return a.Length < b.Length;}// Function to return the count of// valid numbers in the range [l, r]static int findcount(String l, String r){ // Generate all the valid numbers // in the range [1, MAX] generate(); // To store the count of numbers // in the range [l, r] int count = 0; // For every valid number in // the range [1, MAX] for (int i = 0; i < ans.Count; i++) { String a = ans[i]; // If current number is within // the required range if (comp(l, a) && comp(a, r)) { count++; } // If number is equal to either l or r else if (a == l || a == r) { count++; } } return count;}// Driver codepublic static void Main (String[] args){ String l = "1", r = "1000"; Console.WriteLine(findcount(l, r));}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript implementation of the approach// Maximum possible valid numberlet MAX = 543210;// To store all the required number// from the range [1, MAX]let ans = [];// Function that returns true if x// satisfies the given conditionsfunction isValidNum(x){ // To store the digits of x let mp = new Map(); for (let i = 0; i < x.length; i++) { // If current digit appears more than once if (mp.has(x[i].charCodeAt(0) - '0'.charCodeAt(0))) { return false; } // If current digit is greater than 5 else if (x[i].charCodeAt(0) - '0'.charCodeAt(0) > 5) { return false; } // Put the digit in the map else { mp.set(x[i].charCodeAt(0) - '0'.charCodeAt(0), 1); } } return true;}// Function to generate all the required// numbers in the range [1, MAX]function generate(){ // Insert first 5 valid numbers let q = []; q.push("1"); q.push("2"); q.push("3"); q.push("4"); q.push("5"); let flag = true; // Inserting 0 externally because 0 cannot // be the leading digit in any number ans.push("0"); while (q.length!=0) { let x = q.shift(); // If x satisfies the given conditions if (isValidNum(x)) { ans.push(x); } // Cannot append anymore digit as // adding a digit will repeat one of // the already present digits if (x.length == 6) continue; // Append all the valid digits one by // one and push the new generated // number to the queue for (let i = 0; i <= 5; i++) { let z = (i).toString(); // Append the digit let temp = x + z; // Push the newly generated // number to the queue q.push(temp); } }}// Function to compare two Strings// which represent a numerical valuefunction comp(a,b){ if (a.length== b.length) { return a < b ? true : false; } else return a.length < b.length;}// Function to return the count of// valid numbers in the range [l, r]function findcount(l,r){ // Generate all the valid numbers // in the range [1, MAX] generate(); // To store the count of numbers // in the range [l, r] let count = 0; // For every valid number in // the range [1, MAX] for (let i = 0; i < ans.length; i++) { let a = ans[i]; // If current number is within // the required range if (comp(l, a) && comp(a, r)) { count++; } // If number is equal to either l or r else if (a == l || a == r) { count++; } } return count;}// Driver codelet l = "1", r = "1000"; document.write(findcount(l, r));// This code is contributed by unknown2108</script> |
Output
130
Another Approach :
The next valid number in the series can be generated from the previously generated numbers and binary search is used instead of linear search to reduce the time complexity.
C++
#include<bits/stdc++.h>using namespace std;// Function to check if all digits of a number are uniquebool possible(string x){ // creating unordered_map to check if duplicate digit exists unordered_map<char, int> mp; for(char i : x) { if(mp.find(i) == mp.end()) { mp[i] = 1; } else { return false; } } return true;}// Function to create a list containing all // possible no. with unique digits (digits <= 5)void total(vector<string> &a){ // initializing i for the first index of list 'a' int i = 1; // traversing till i is less than length of list 'a' while(i < a.size()) { // considering ith index value of list 'a' string x = a[i]; i++; // Cannot append anymore digit as // adding a digit will repeat one // of the already present digits if(x.size() == 5) { continue; } // Append all the valid digits one // by one and append the new generated for(int j = 0; j <= 5; j++) { // Append the digit string z = to_string(j); // If combination satisfies the given conditions if(possible(x + z)) { // Push the newly generated a.push_back(x+z); } } }}// Function to print the count within range using binary searchvoid PrintSolution(vector<string> &a, int l, int r) { int ans1 = 0, ans2 = 0; int low = 0, high = a.size()-1; // finding the index for l while(low <= high) { int mid = (low+high)/2; if(stoi(a[mid]) == l) { ans1 = mid; break; } else if(stoi(a[mid]) > l) { ans1 = mid; high = mid - 1; } else { low = mid + 1; } } low = 0; high = a.size()-1; // finding index for r while(low <= high) { int mid = (low+high)/2; if(stoi(a[mid]) == r) { ans2 = mid; break; } else if(stoi(a[mid]) < r) { ans2 = mid; low = mid + 1; } else { high = mid - 1; } } cout << ans2-ans1+1 << endl;}// Driver Codeint main() { vector<string> a = {"0", "1", "2", "3", "4", "5"}; // calling function to calculate all possible combination available total(a); int l = 1, r = 1000; PrintSolution(a, l, r); return 0;} |
Java
import java.util.*;public class UniqueDigits{ // function to check if a number has unique digits public static boolean possible(String x) { // creating a HashMap to check if duplicate digit exists HashMap<Character, Integer> d = new HashMap<>(); for (int i = 0; i < x.length(); i++) { char c = x.charAt(i); if (!d.containsKey(c)) { d.put(c, 1); } else { return false; } } return true; } // function to create a list containing all possible numbers // with unique digits. digits <= 5. public static void total(ArrayList<String> a) { // initializing i for the first index of list 'a' int i = 1; // traversing till i is less than length of list 'a' while (i < a.size()) { // considering ith index value of list 'a' String x = a.get(i); i++; // Cannot append anymore digit as // adding a digit will repeat one of // the already present digits if (x.length() == 5) { continue; } // Append all the valid digits one by // one and append the new generated for (int j = 0; j <= 5; j++) { // Append the digit String z = Integer.toString(j); // If combination satisfies the given conditions if (possible(x + z)) { // Push the newly generated a.add(x + z); } } } } // function to print the count within range using binary search public static void printSolution(ArrayList<String> a, int l, int r) { int ans1 = 0, ans2 = 0; int low = 0, high = a.size() - 1; // finding the index for l while (low <= high) { int mid = (low + high) / 2; if (Integer.parseInt(a.get(mid)) == l) { ans1 = mid; break; } if (Integer.parseInt(a.get(mid)) > l) { ans1 = mid; high = mid - 1; } else { low = mid + 1; } } low = 0; high = a.size() - 1; // finding the index for r while (low <= high) { int mid = (low + high) / 2; if (Integer.parseInt(a.get(mid)) == r) { ans2 = mid; break; } if (Integer.parseInt(a.get(mid)) < r) { ans2 = mid; low = mid + 1; } else { high = mid - 1; } } System.out.println(ans2 - ans1 + 1); } // main driver code public static void main(String[] args) { ArrayList<String> a = new ArrayList<String>(Arrays.asList("0", "1", "2", "3", "4", "5")); // calling function to calculate // all possible combination available total(a); int l = 1, r = 1000; printSolution(a, l, r); }} |
Python3
# Python3 implementation of the approach# for checking if number has all unique digitsdef possible(x): # creating dictionary to check if duplicate digit exists d = {} for i in x: if i not in d: d[i] = 1 else: return 0 return 1# to create a list containing all possible no.# with unique digits#digits <= 5def total(a): # initializing i for the first index of list 'a' i = 1 # traversing till i is less than length of list 'a' while i < len(a): # considering ith index value of list 'a' x = a[i] i += 1 # Cannot append anymore digit as # adding a digit will repeat one of # the already present digits if len(x) == 6: continue # Append all the valid digits one by # one and append the new generated for j in range(6): # Append the digit z = str(j) # If combination satisfies the given conditions if possible(x+z): # Push the newly generated a.append(x+z)# function to print the count within range# using binary searchdef PrintSolution(a, l, r): ans1 = ans2 = 0 low = 0 high = len(a)-1 # finding the index for l while low <= high: mid = (low+high)//2 if int(a[mid]) == l: ans1 = mid break if int(a[mid]) > l: ans1 = mid high = mid - 1 else: low = mid + 1 low = 0 high = len(a) - 1 # finding index for r while low <= high: mid = (low+high)//2 if int(a[mid]) == r: ans2 = mid break if int(a[mid]) < r: ans2 = mid low = mid + 1 else: high = mid - 1 print(ans2-ans1+1)# Driver Codea = ['0', '1', '2', '3', '4', '5']# calling function to calculate# all possible combination availabletotal(a)l = 1r = 1000PrintSolution(a, l, r)# This code is contributed by Anvesh Govind Saxena |
C#
using System;using System.Collections.Generic;public class UniqueDigits{ // function to check if a number has unique digits public static bool Possible(string x) { // creating a Dictionary to check if duplicate digit exists Dictionary<char, int> d = new Dictionary<char, int>(); for (int i = 0; i < x.Length; i++) { char c = x[i]; if (!d.ContainsKey(c)) { d.Add(c, 1); } else { return false; } } return true; } // function to create a list containing all possible numbers // with unique digits. digits <= 5. public static void Total(List<string> a) { // initializing i for the first index of list 'a' int i = 1; // traversing till i is less than length of list 'a' while (i < a.Count) { // considering ith index value of list 'a' string x = a[i]; i++; // Cannot append anymore digit as // adding a digit will repeat one of // the already present digits if (x.Length == 5) { continue; } // Append all the valid digits one by // one and append the new generated for (int j = 0; j <= 5; j++) { // Append the digit string z = j.ToString(); // If combination satisfies the given conditions if (Possible(x + z)) { // Push the newly generated a.Add(x + z); } } } } // function to print the count within range using binary search public static void PrintSolution(List<string> a, int l, int r) { int ans1 = 0, ans2 = 0; int low = 0, high = a.Count - 1; // finding the index for l while (low <= high) { int mid = (low + high) / 2; if (int.Parse(a[mid]) == l) { ans1 = mid; break; } if (int.Parse(a[mid]) > l) { ans1 = mid; high = mid - 1; } else { low = mid + 1; } } low = 0; high = a.Count - 1; // finding the index for r while (low <= high) { int mid = (low + high) / 2; if (int.Parse(a[mid]) == r) { ans2 = mid; break; } if (int.Parse(a[mid]) < r) { ans2 = mid; low = mid + 1; } else { high = mid - 1; } } Console.WriteLine(ans2 - ans1 + 1); } // main driver code public static void Main(string[] args) { List<string> a = new List<string>(new string[] { "0", "1", "2", "3", "4", "5" }); // calling function to calculate // all possible combination available Total(a); int l = 1, r = 1000; PrintSolution(a, l, r); }} |
Javascript
// JavaScript implementation of the approach// for checking if number has all unique digits// creating function to check if duplicate digit existsfunction possible(x) { // creating dictionary to check if duplicate digit exists var d = {}; for (var i = 0; i < x.length; i++) { if (!(x[i] in d)) { d[x[i]] = 1; } else { return 0; } } return 1;}// to create a list containing all possible no.// with unique digits// digits <= 5function total(a) { // initializing i for the first index of list 'a' var i = 1; // traversing till i is less than length of list 'a' while (i < a.length) { // considering ith index value of list 'a' var x = a[i]; i += 1; // Cannot append anymore digit as // adding a digit will repeat one of // the already present digits if (x.length == 6) { continue; } // Append all the valid digits one by // one and append the new generated for (var j = 0; j < 6; j++) { // Append the digit var z = j.toString(); // If combination satisfies the given conditions if (possible(x + z)) { // Push the newly generated a.push(x + z); } } }}// function to print the count within range// using binary searchfunction PrintSolution(a, l, r) { var ans1 = 0; var ans2 = 0; var low = 0; var high = a.length - 1; // finding the index for l while (low <= high) { var mid = Math.floor((low + high) / 2); if (parseInt(a[mid]) === l) { ans1 = mid; break; } if (parseInt(a[mid]) > l) { ans1 = mid; high = mid - 1; } else { low = mid + 1; } } low = 0; high = a.length - 1; // finding index for r while (low <= high) { var mid = Math.floor((low + high) / 2); if (parseInt(a[mid]) === r) { ans2 = mid; break; } if (parseInt(a[mid]) < r) { ans2 = mid; low = mid + 1; } else { high = mid - 1; } } console.log(ans2 - ans1 + 1);}// Driver Codevar a = ['0', '1', '2', '3', '4', '5'];// calling function to calculate// all possible combination availabletotal(a);var l = 1;var r = 1000;PrintSolution(a, l, r);// This code is contributed by phasing17 |
Output
130
Approach: Recursive Backtracking with Set-based Pruning
The steps of the “Recursive Backtracking with Set-based Pruning” approach are:
- Define a helper function count_numbers that takes a length n, a lower bound L, an upper bound R, and a set used that stores the digits already used in the current number.
- If n is zero, convert the current number stored in the list curr to an integer, and check if it satisfies the conditions: (a) the number is within the range [L, R], and (b) all its digits are distinct.
- If the conditions are satisfied, return 1 to indicate that a valid number is found. Otherwise, return 0.
- Initialize a counter count to zero, and loop over all possible digits d from 0 to 5.
- If d is zero and the length of curr is zero, skip this digit (because it cannot be the leading digit).
- If d is greater than 5, break the loop (because we have already checked all possible digits).
- If d is not in the set used, add it to used, append it to curr, and recursively call count_numbers with n-1, L, R, and used.
- After the recursive call, pop d from curr and remove it from used.
- Add the return value from the recursive call to the counter count.
- Return the final value of count after all recursive calls.
- In the main function count_distinct_numbers, loop over all possible lengths n from 1 to the number of digits in the upper bound R.
- For each length n, initialize an empty set used and an empty list curr, and call the helper function count_numbers with n, L, R, and used.
- Add the return value from count_numbers to a running total count.
- Return the final value of count after all iterations.
C++
#include <iostream>#include <set>#include <string>#include <vector>using namespace std;int count_numbers(int n, int L, int R, set<int>& used, vector<int>& curr){ if (n == 0) { int num = stoi(to_string(curr[0])); for (int i = 1; i < curr.size(); i++) { num = num * 10 + curr[i]; } if (num >= L && num <= R && set<int>(curr.begin(), curr.end()).size() == curr.size()) { return 1; } else { return 0; } } int count = 0; for (int d = 0; d <= 5; d++) { if (d == 0 && curr.empty()) { continue; } if (d > 5) { break; } if (!used.count(d)) { used.insert(d); curr.push_back(d); count += count_numbers(n - 1, L, R, used, curr); curr.pop_back(); used.erase(d); } } return count;}int count_distinct_numbers(int L, int R){ int count = 0; for (int n = 1; n <= to_string(R).size(); n++) { set<int> used; vector<int> curr; count += count_numbers(n, L, R, used, curr); } return count;}int main(){ int L = 100; int R = 1000; cout << count_distinct_numbers(L, R) << endl; // Output: 100 return 0;} |
Java
import java.util.*;public class Solution { public static int countDistinctNumbers(int L, int R) { int count = 0; for (int n = 1; n <= Integer.toString(R).length(); n++) { Set<Integer> used = new HashSet<>(); List<Integer> curr = new ArrayList<>(); count += countNumbers(n, L, R, used, curr); } return count; } private static int countNumbers(int n, int L, int R, Set<Integer> used, List<Integer> curr) { if (n == 0) { int num = Integer.parseInt(curr.stream().map(String::valueOf).reduce("", String::concat)); if (L <= num && num <= R && new HashSet<>(curr).size() == curr.size()) { return 1; } else { return 0; } } int count = 0; for (int d = 0; d <= 5; d++) { if (d == 0 && curr.isEmpty()) { continue; } if (used.contains(d)) { continue; } used.add(d); curr.add(d); count += countNumbers(n-1, L, R, used, curr); curr.remove(curr.size()-1); used.remove(d); } return count; } public static void main(String[] args) { int L = 100; int R = 1000; System.out.println(countDistinctNumbers(L, R)); // Output: 100 }} |
Python3
def count_distinct_numbers(L, R): def count_numbers(n, L, R, used): if n == 0: num = int("".join(map(str, curr))) if L <= num <= R and len(set(curr)) == len(curr): return 1 else: return 0 count = 0 for d in range(6): if d == 0 and len(curr) == 0: continue if d > 5: break if d not in used: used.add(d) curr.append(d) count += count_numbers(n-1, L, R, used) curr.pop() used.remove(d) return count count = 0 for n in range(1, len(str(R))+1): used = set() curr = [] count += count_numbers(n, L, R, used) return count#ExampleL = 100R = 1000print(count_distinct_numbers(L, R)) # Output: 100 |
C#
using System;using System.Collections.Generic;namespace CountDistinctNumbers{ class Program { static int CountNumbers(int n, int L, int R, HashSet<int> used, List<int> curr) { if (n == 0) { int num = int.Parse(curr[0].ToString()); for (int i = 1; i < curr.Count; i++) { num = num * 10 + curr[i]; } if (num >= L && num <= R && new HashSet<int>(curr).Count == curr.Count) { return 1; } else { return 0; } } int count = 0; for (int d = 0; d <= 5; d++) { if (d == 0 && curr.Count == 0) { continue; } if (d > 5) { break; } if (!used.Contains(d)) { used.Add(d); curr.Add(d); count += CountNumbers(n - 1, L, R, used, curr); curr.RemoveAt(curr.Count - 1); used.Remove(d); } } return count; } static int CountDistinctNumbers(int L, int R) { int count = 0; for (int n = 1; n <= R.ToString().Length; n++) { HashSet<int> used = new HashSet<int>(); List<int> curr = new List<int>(); count += CountNumbers(n, L, R, used, curr); } return count; } static void Main(string[] args) { int L = 100; int R = 1000; Console.WriteLine(CountDistinctNumbers(L, R)); // Output: 100 } }} |
Javascript
function count_distinct_numbers(L, R) { let curr = []; function count_numbers(n, L, R, used) { if (n === 0) { let num = parseInt(curr.join('')); if (L <= num && num <= R && new Set(curr).size === curr.length) { return 1; } else { return 0; } } let count = 0; for (let d = 0; d < 6; d++) { if (d === 0 && curr.length === 0) { continue; } if (d > 5) { break; } if (!used.has(d)) { used.add(d); curr.push(d); count += count_numbers(n - 1, L, R, used); curr.pop(); used.delete(d); } } return count; } let count = 0; for (let n = 1; n <= String(R).length; n++) { let used = new Set(); count += count_numbers(n, L, R, used); } return count;}// Examplelet L = 100;let R = 1000;console.log(count_distinct_numbers(L, R)); // Output: 100 |
Output
100
The time complexity of this approach is O(N^2), where N is the number of digits in the upper bound R.
The Auxiliary space is also O(N^2),
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
