Count of numbers in the range [L, R] which satisfy the given conditions

0 0 22 minutes read

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 conditions
bool 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 value
bool 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 code
int main()
{
 
    string l = "1", r = "1000";
 
    cout << findcount(l, r);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Maximum possible valid number
static 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 conditions
static 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 value
static 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 code
public 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 approach
from collections import deque
 
# Maximum possible valid number
MAX = 543210
 
# To store all the required number
# from the range [1, MAX]
ans = []
 
# Function that returns true if x
# satisfies the given conditions
def 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 value
def 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 code
l = "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 number
static 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 conditions
static 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 value
static 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 code
public 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 number
let MAX = 543210;
 
// To store all the required number
// from the range [1, MAX]
let ans = [];
 
// Function that returns true if x
// satisfies the given conditions
function 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 value
function 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 code
let l = "1", r = "1000";
   
document.write(findcount(l, r));
 
 
// This code is contributed by unknown2108
 
</script>

Output

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 unique
bool 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 search
void 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 Code
int 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 digits
 
 
def 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 <= 5
 
 
def 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 search
 
 
def 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 Code
a = ['0', '1', '2', '3', '4', '5']
 
# calling function to calculate
# all possible combination available
total(a)
 
l = 1
r = 1000
 
PrintSolution(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 exists
function 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 <= 5
function 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 search
function 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 Code
var a = ['0', '1', '2', '3', '4', '5'];
 
// calling function to calculate
// all possible combination available
total(a);
 
var l = 1;
var r = 1000;
 
PrintSolution(a, l, r);
 
// This code is contributed by phasing17

Output

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
 
#Example
L = 100
R = 1000
print(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;
}
 
// Example
let L = 100;
let R = 1000;
console.log(count_distinct_numbers(L, R)); // Output: 100

Output

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 zambiatek!