Given an integer N, the task is to find the count of N-digit numbers with all distinct digits.
Examples:
Input: N = 1
Output: 9
1, 2, 3, 4, 5, 6, 7, 8 and 9 are the 1-digit numbers
with all distinct digits.
Input: N = 3
Output: 648
Naive Approach: If N > 10 i.e. there will be atleast one digit which will be repeating hence for such cases the answer will be 0 else for the values of N = 1, 2, 3, …, 9, a series will be formed as 9, 81, 648, 4536, 27216, 136080, 544320, … whose Nth term will be 9 * 9! / (10 – N)!.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the factorial of nint factorial(int n){ if (n == 0) return 1; return n * factorial(n - 1);}// Function to return the count// of n-digit numbers with// all distinct digitsint countNum(int n){ if (n > 10) return 0; return (9 * factorial(9) / factorial(10 - n));}// Driver codeint main(){ int n = 3; cout << countNum(n); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the factorial of n static int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } // Function to return the count // of n-digit numbers with // all distinct digits static int countNum(int n) { if (n > 10) return 0; return (9 * factorial(9) / factorial(10 - n)); } // Driver code public static void main(String []args) { int n = 3; System.out.println(countNum(n)); }}// This code is contributed by Srathore |
Python3
# Python3 implementation of the approach # Function to return the factorial of n def factorial(n) : if (n == 0) : return 1; return n * factorial(n - 1); # Function to return the count # of n-digit numbers with # all distinct digits def countNum(n) : if (n > 10) : return 0; return (9 * factorial(9) // factorial(10 - n)); # Driver code if __name__ == "__main__" : n = 3; print(countNum(n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{ // Function to return the factorial of n static int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } // Function to return the count // of n-digit numbers with // all distinct digits static int countNum(int n) { if (n > 10) return 0; return (9 * factorial(9) / factorial(10 - n)); } // Driver code public static void Main(String []args) { int n = 3; Console.WriteLine(countNum(n)); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Function to return the factorial of nfunction factorial(n){ if (n == 0) return 1; return n * factorial(n - 1);}// Function to return the count// of n-digit numbers with// all distinct digitsfunction countNum(n){ if (n > 10) return 0; return (9 * factorial(9) / factorial(10 - n));}// Driver codevar n = 3;document.write(countNum(n));// This code is contributed by rutvik_56.</script> |
Output
648
Time Complexity: O(n)
Auxiliary Space: O(n)
Efficient Approach: We have to fill (n) places with different digit. Like we n=2 then (_ _) places to fill. first place we fill (1 to 9) any number. let we fill 9 in first place then in second place we have choice (0 to 8). So for first place we 9 choices because we can not fill 0 at first place and after that for 2nd place we 9 choice and for 3rd place we 8 choice then so on…
let we take 4 digit no so ( 9choice 9 choice 8 choice 7choice) .
Choices->
first place -9
second place-9
third place -8
fourth place -7
and so on…….
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of n-digit numbers with// all distinct digitslong long countNum(int n){ if (n > 10) return 0; long long count = 1; // Store the count long long j = 9; // take choice /* take loop 1 to n and multiply with choice*/ for (int i = 1; i <= n; i++) { if (i == 1) { count = count * j; continue; } else { count = count * j; j--; } } return count;}// Driver codeint main(){ int n = 3; cout << countNum(n); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to return the count // of n-digit numbers with // all distinct digits static long countNum(int n) { if (n > 10) return 0; long count = 1; // Store the count long j = 9; // take choice /* take loop 1 to n and multiply with choice*/ for (int i = 1; i <= n; i++) { if (i == 1) { count = count * j; continue; } else { count = count * j; j--; } } return count; } // Driver code public static void main(String[] args) { int n = 3; System.out.println(countNum(n)); }}// This code is contributed by Srathore |
Python3
# Python implementation of the approach# Function to return the count# of n-digit numbers with# all distinct digitsdef countNum(n): if n > 10: return 0 count = 1 # Store the count j = 9 # take choice # take loop 1 to n and multiply with choice for i in range(1, n+1): if i == 1: count = count * j continue else: count = count * j j -= 1 return count# Driver coden = 3print(countNum(n))# This code is contributed by rutikbhosale |
C#
using System;class GFG{ // Function to return the count // of n-digit numbers with // all distinct digits static long countNum(int n) { if (n > 10) return 0; long count = 1; // Store the count long j = 9; // take choice /* take loop 1 to n and multiply with choice*/ for (int i = 1; i <= n; i++) { if (i == 1) { count = count * j; continue; } else { count = count * j; j--; } } return count; } // Driver code static void Main(string[] args) { int n = 3; Console.WriteLine(countNum(n)); }} |
Javascript
// Javascript implementation of the approach// Function to return the count// of n-digit numbers with// all distinct digitsfunction countNum(n) { if (n > 10) return 0; let count = 1; // Store the count let j = 9; // take choice /* take loop 1 to n and multiply with choice*/ for (let i = 1; i <= n; i++) { if (i === 1) { count *= j; continue; } else { count *= j; j--; } } return count;}// Driver codeconst n = 3;console.log(countNum(n)); |
Output
648
Time Complexity: O(n)
Auxiliary Space: O(1)
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!
