Given an integer N, the task is to count the numbers less than or equal to N such that each number contains at least one repeated digit.
Examples:
Input: N = 20
Output: 1
Explanation:
Numbers containing at least one repeated digit and less than or equal to N(= 20) are {11}.
Therefore, the required output is 1.Input: N = 100
Output: 10
Explanation:
Numbers containing at least one repeated digit and less than or equal to N(= 100) are {11, 22, 33, 44, 55, 66, 77, 88, 99, 100}.
Therefore, the required output is 10.
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say X, to store the total count of digits in N.
- Initialize a variable, say cntNumbers, to store the total count of numbers less than or equal to N consisting of unique digits.
- Calculate the total count of X-digit numbers which contains unique digits and update cntNumbers. Below is the formula to calculate total count of X-digit numbers with all unique digits.
Total count of X-digit numbers with all unique digits = {(9 * factorial(9)) / factorial(10 – X)}
- Calculate total count of X-digit numbers less than or equal to N which contains unique digits by checking all possible values at each possible digits of a number less than or equal to N and update cntNumbers.
- Finally, print the value of (N – cntNumbers).
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h>using namespace std;long factorial(int n) { return (n == 1 || n == 0) ? 1 : n * factorial(n - 1); }// Function to count arrangements to // select K elements from N elements long NPR(int n, int k){ return factorial(n) / factorial(n - k);}// Function to count numbers less than or equal // to N with at least one repeated digits int cntNumLessThanEqualNRepeatedDigits(int N){ // Stores the value of N int temp = N; // Stores count of // digits in N int X = 0; // Store all possible // digits of N vector<int> nums; // Calculate digits in N while(temp) { // Update X X += 1; // Insert digits of N // into nums nums.push_back(temp % 10); // Update temp temp /= 10; } reverse(nums.begin(), nums.end()); // Count numbers of (X)-digit // with no repeated digits int cntNumbers = 0; // Calculate count of numbers of less than // (X)-digit and no repeated digits for(int i = 1; i < X; i++) { // Update cntnumbers cntNumbers += 9 * (factorial(9) / factorial(10 - i)); } // Stores unique digits of // (X)-digit numbers unordered_set<int> vis; // Calculate (X) digits // numbers with no repeated digits for(int i = 0; i < nums.size(); i++) { // Stores count of unique // value at i_th digit int k = 0; // Stores minimum possible value of // i_th digit of a number int Min = 0; // If current digit is the first // digit of a number if (i == 0) { // Update Min Min = 1; } else { // Update Min Min = 0; } // Stores maximum possible value of // i_th digit if a number int Max = 0; // If current digit is the last // digit of a number if (i == X - 1) { // Update Max Max = nums[i]; } else { // Update Max Max = nums[i] - 1; } // Iterate over all possible value // of current digit for(int j = Min; j <= Max; j++) { // If value of current digit // already occurred in vis if (vis.find(j) != vis.end()) { continue; } // Update k k += 1; } // Update cntNumbers cntNumbers += k * (NPR(9 - i, X - i - 1)); // If current value of i-th digit // already occurred in vis if (vis.find(nums[i]) != vis.end()) { break; } // Insert val in vis vis.insert(nums[i]); } // Return total count of numbers less // than or equal to N with repetition return (N - cntNumbers);}// Driver Code int main(){ int N = 100; cout << cntNumLessThanEqualNRepeatedDigits(N); return 0;}// This code is contributed by Manu Pathria |
Java
// Java program to implement // the above approach import java.io.*;import java.util.*;class GFG{ public static int factorial(int n) { return (n == 1 || n == 0) ? 1 : n * factorial(n - 1); }// Function to count arrangements to // select K elements from N elements public static int NPR(int n, int k){ return factorial(n) / factorial(n - k);}// Function to count numbers less than or equal // to N with at least one repeated digits public static int cntNumLessThanEqualNRepeatedDigits(int N){ // Stores the value of N int temp = N; // Stores count of // digits in N int X = 0; // Store all possible // digits of N List<Integer> nums = new ArrayList<>(); // Calculate digits in N while (temp > 0) { // Update X X += 1; // Insert digits of N // into nums nums.add(temp % 10); // Update temp temp /= 10; } Collections.reverse(nums); // Count numbers of (X)-digit // with no repeated digits int cntNumbers = 0; // Calculate count of numbers of less than // (X)-digit and no repeated digits for(int i = 1; i < X; i++) { // Update cntnumbers cntNumbers += 9 * (factorial(9) / factorial(10 - i)); } // Stores unique digits of // (X)-digit numbers Set<Integer> vis=new HashSet<>(); // Calculate (X) digits // numbers with no repeated digits for(int i = 0; i < nums.size(); i++) { // Stores count of unique // value at i_th digit int k = 0; // Stores minimum possible value of // i_th digit of a number int Min = 0; // If current digit is the first // digit of a number if (i == 0) { // Update Min Min = 1; } else { // Update Min Min = 0; } // Stores maximum possible value of // i_th digit if a number int Max = 0; // If current digit is the last // digit of a number if (i == X - 1) { // Update Max Max = nums.get(i); } else { // Update Max Max = nums.get(i) - 1; } // Iterate over all possible value // of current digit for(int j = Min; j <= Max; j++) { // If value of current digit // already occurred in vis if (vis.contains(j)) { continue; } // Update k k += 1; } // Update cntNumbers cntNumbers += k * (NPR(9 - i, X - i - 1)); // If current value of i-th digit // already occurred in vis if (vis.contains(nums.get(i))) { break; } // Insert val in vis vis.add(nums.get(i)); } // Return total count of numbers less // than or equal to N with repetition return (N - cntNumbers);}// Driver Code public static void main(String[] args){ int N = 100; System.out.print( cntNumLessThanEqualNRepeatedDigits(N));}}// This code is contributed by Manu Pathria |
Python3
# Python3 program to implement# the above approachimport math# Function to count arrangements to# select K elements from N elements def NPR(n, k): return (math.factorial(n) // math.factorial(n-k))# Function to count numbers less than or equal # to N with at least one repeated digitsdef cntNumLessThanEqualNRepeatedDigits(N): # Stores the value of N temp = N # Stores count of # digits in N X = 0; # Store all possible # digits of N nums = [] # Calculate digits in N while(temp): # Update X X += 1 # Insert digits of N # into nums nums.append(temp % 10) # Update temp temp //= 10 # Reverse nums nums.reverse() # Count numbers of (X)-digit # with no repeated digits cntNumbers = 0 # Calculate count of numbers of less than # (X)-digit and no repeated digits for i in range(1, X): # Update cntnumbers cntNumbers += 9 * (math.factorial(9) // math.factorial(10 - i)) # Stores unique digits of # (X)-digit numbers vis = set() # Calculate (X) digits # numbers with no repeated digits for i, val in enumerate(nums): # Stores count of unique # value at i_th digit k = 0 # Stores minimum possible value of # i_th digit of a number Min = 0; # If current digit is the first # digit of a number if i == 0: #Update Min Min = 1 else: # Update Min Min = 0 # Stores maximum possible value of # i_th digit if a number Max = 0; # If current digit is the last # digit of a number if i == X - 1: # Update Max Max = val else: # Update Max Max = val - 1; # Iterate over all possible value # of current digit for j in range(Min, Max + 1): # If value of current digit # already occurred in vis if (j in vis): continue # Update k k += 1 # Update cntNumbers cntNumbers += k * (NPR(9 - i, X - i - 1)) # If current value of i-th digit # already occurred in vis if val in vis: break # Insert val in vis vis.add(val) # Return total count of numbers less # than or equal to N with repetition return (N - cntNumbers)# Driver Codeif __name__ == '__main__': N = 100 # Function call print(cntNumLessThanEqualNRepeatedDigits(N)) |
C#
// C# program to implement // the above approach using System;using System.Collections.Generic;class GFG { static int factorial(int n) { return (n == 1 || n == 0) ? 1 : n * factorial(n - 1); } // Function to count arrangements to // select K elements from N elements static int NPR(int n, int k) { return factorial(n) / factorial(n - k); } // Function to count numbers less than or equal // to N with at least one repeated digits static int cntNumLessThanEqualNRepeatedDigits(int N) { // Stores the value of N int temp = N; // Stores count of // digits in N int X = 0; // Store all possible // digits of N List<int> nums = new List<int>(); // Calculate digits in N while (temp > 0) { // Update X X += 1; // Insert digits of N // into nums nums.Add(temp % 10); // Update temp temp /= 10; } nums.Reverse(); // Count numbers of (X)-digit // with no repeated digits int cntNumbers = 0; // Calculate count of numbers of less than // (X)-digit and no repeated digits for(int i = 1; i < X; i++) { // Update cntnumbers cntNumbers += 9 * (factorial(9) / factorial(10 - i)); } // Stores unique digits of // (X)-digit numbers HashSet<int> vis = new HashSet<int>(); // Calculate (X) digits // numbers with no repeated digits for(int i = 0; i < nums.Count; i++) { // Stores count of unique // value at i_th digit int k = 0; // Stores minimum possible value of // i_th digit of a number int Min = 0; // If current digit is the first // digit of a number if (i == 0) { // Update Min Min = 1; } else { // Update Min Min = 0; } // Stores maximum possible value of // i_th digit if a number int Max = 0; // If current digit is the last // digit of a number if (i == X - 1) { // Update Max Max = nums[i]; } else { // Update Max Max = nums[i] - 1; } // Iterate over all possible value // of current digit for(int j = Min; j <= Max; j++) { // If value of current digit // already occurred in vis if (vis.Contains(j)) { continue; } // Update k k += 1; } // Update cntNumbers cntNumbers += k * (NPR(9 - i, X - i - 1)); // If current value of i-th digit // already occurred in vis if (vis.Contains(nums[i])) { break; } // Insert val in vis vis.Add(nums[i]); } // Return total count of numbers less // than or equal to N with repetition return (N - cntNumbers); } static void Main() { int N = 100; Console.WriteLine(cntNumLessThanEqualNRepeatedDigits(N)); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program to implement // the above approach function factorial(n) { return (n == 1 || n == 0) ? 1 : n * factorial(n - 1); }// Function to count arrangements to // select K elements from N elements function NPR(n, k){ return factorial(n) / factorial(n - k);}// Function to count numbers less than or equal // to N with at least one repeated digits function cntNumLessThanEqualNRepeatedDigits(N){ // Stores the value of N var temp = N; // Stores count of // digits in N var X = 0; // Store all possible // digits of N var nums = []; // Calculate digits in N while(temp) { // Update X X += 1; // Insert digits of N // into nums nums.push(temp % 10); // Update temp temp = parseInt(temp/10); } nums.reverse(); // Count numbers of (X)-digit // with no repeated digits var cntNumbers = 0; // Calculate count of numbers of less than // (X)-digit and no repeated digits for(var i = 1; i < X; i++) { // Update cntnumbers cntNumbers += 9 * (factorial(9) / factorial(10 - i)); } // Stores unique digits of // (X)-digit numbers var vis = new Set(); // Calculate (X) digits // numbers with no repeated digits for(var i = 0; i < nums.length; i++) { // Stores count of unique // value at i_th digit var k = 0; // Stores minimum possible value of // i_th digit of a number var Min = 0; // If current digit is the first // digit of a number if (i == 0) { // Update Min Min = 1; } else { // Update Min Min = 0; } // Stores maximum possible value of // i_th digit if a number var Max = 0; // If current digit is the last // digit of a number if (i == X - 1) { // Update Max Max = nums[i]; } else { // Update Max Max = nums[i] - 1; } // Iterate over all possible value // of current digit for(var j = Min; j <= Max; j++) { // If value of current digit // already occurred in vis if (vis.has(j)) { continue; } // Update k k += 1; } // Update cntNumbers cntNumbers += k * (NPR(9 - i, X - i - 1)); // If current value of i-th digit // already occurred in vis if (vis.has(nums[i])) { break; } // Insert val in vis vis.add(nums[i]); } // Return total count of numbers less // than or equal to N with repetition return (N - cntNumbers);}// Driver Code var N = 100;document.write( cntNumLessThanEqualNRepeatedDigits(N));// This code is contributed by rutvik_56.</script> |
Output:
10
Time Complexity: O((log10N)2)
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!
