Last Updated on March 28, 2022 by Ria Pathak
Concepts Used
Back Tracking
Difficulty Level
Medium
Problem Statement :
Given
N, count all the numbers with unique digits less than 10n.
See original problem statement here
Solution Approach :
Introduction :
Idea is to traverse all the numbers less than 10n, and count the numbers with unique digits.
Method 1 (Brute-Force):
In this method, we will traverse all the possible numbers. Mark each digit of the number as visited and when any other digit came up which is visited, discard that number. Increment the number count when all the digits of a number are visited and every digit is visited exactly once (No digits are repeated).
Method 2 (Backtracking):
Above approach checks all the combinations one after one upto 10n. In other words the above approach will iterate upto 10n which is beyond the time limit.
In this method we will use backtracking to solve the above problem.
Backtracking is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
We will store the count of unique digits for each digit (1-n).
Now for every digit there are atmost 10 choices (0-9). Each time we visit a digit we will mark it as visited so that we wont visit any digit more than once. Now storing the count of individual digits and adding all the counts of individual digits we get our final answer.
Algorithm :
Back():
- If
index == target, increment the count. - else, for every
k= 0to9:- if current digit is not visited, mark it visited and,
- call back(target,index+1,n)
- mark the current digit unvisited (backtracking step).
Complexity Analysis :
In the first method we are check all the numbers from
0to 10n. So the time complexity is 10n.
Solutions:
#include <stdio.h>
int back(int target, int idx, int* visit) {
if (idx == target)
return 1;
int count = 0;
for (int i = idx?0:1; i < 10; i++) {
if (!visit[i]) {
visit[i] = 1;
count += back(target, idx+1, visit);
visit[i] = 0;
}
}
return count;
}
int solve(int n) {
int visit[10] = {0};
int count = 0;
for (int i = 0; i <= n; i++)
count += back(i, 0, visit);
return count;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",solve(n));
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int back(int target, int idx, bool* visit)
{
if (idx == target)
return 1;
int count = 0;
for (int i = (idx==0)?1:0; i < 10; i++)
{
if (!visit[i])
{
visit[i] = true;
count += back(target, idx+1, visit);
visit[i] = false;
}
}
return count;
}
int solve(int n) {
bool visit[10] = {false};
int count = 0;
for (int i = 0; i <=n; i++)
count += back(i, 0, visit);
return count;
}
int main()
{
int n;
cin>>n;
cout<<solve(n)<<endl;
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static int countNumbersWithUniqueDigits(int n) {
if (n > 10) {
return countNumbersWithUniqueDigits(10);
}
int count = 1; // x == 0
long max = (long) Math.pow(10, n);
boolean[] used = new boolean[10];
for (int i = 1; i < 10; i++) {
used[i] = true;
count += search(i, max, used);
used[i] = false;
}
return count;
}
private static int search(long prev, long max, boolean[] used) {
int count = 0;
if (prev < max) {
count += 1;
} else {
return count;
}
for (int i = 0; i < 10; i++) {
if (!used[i]) {
used[i] = true;
long cur = 10 * prev + i;
count += search(cur, max, used);
used[i] = false;
}
}
return count;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(countNumbersWithUniqueDigits(n));
}
}
[forminator_quiz id="2040"]
This article tried to discuss Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.