Given two integer L and R representing a range [L, R], the task is to find the count of integers from the range that are composed of a single distinct digit.
Examples:
Input : L = 9, R = 11 Output : 2 Only 9 and 11 have single distinct digit Input : L = 10, R = 50 Output : 4 11, 22, 33 and 44 are the only valid numbers
Naive Approach: Iterate through all the numbers and check if the number is composed of a single distinct digit only.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Boolean function to check// distinct digits of a numberbool checkDistinct(int x){ // Take last digit int last = x % 10; // Check if all other digits // are same as last digit while (x) { if (x % 10 != last) return false; // Remove last digit x = x / 10; } return true;}// Function to return the count of integers that// are composed of a single distinct digit onlyint findCount(int L, int R){ int count = 0; for (int i = L; i <= R; i++) { // If i has single distinct digit if (checkDistinct(i)) count += 1; } return count;}// Driver codeint main(){ int L = 10, R = 50; cout << findCount(L, R); return 0;} |
Java
//Java implementation of the approachimport java.io.*;class GFG { // Boolean function to check// distinct digits of a numberstatic boolean checkDistinct(int x){ // Take last digit int last = x % 10; // Check if all other digits // are same as last digit while (x >0) { if (x % 10 != last) return false; // Remove last digit x = x / 10; } return true;}// Function to return the count of integers that// are composed of a single distinct digit onlystatic int findCount(int L, int R){ int count = 0; for (int i = L; i <= R; i++) { // If i has single distinct digit if (checkDistinct(i)) count += 1; } return count;}// Driver code public static void main (String[] args) { int L = 10, R = 50; System.out.println (findCount(L, R)); }//This code is contributed by ajit. } |
Python3
# Python3 implementation of above approach# Boolean function to check # distinct digits of a number def checkDistinct(x): # Take last digit last = x % 10 # Check if all other digits # are same as last digit while (x): if (x % 10 != last): return False # Remove last digit x = x // 10 return True# Function to return the count of # integers that are composed of a # single distinct digit only def findCount(L, R): count = 0 for i in range(L, R + 1): # If i has single distinct digit if (checkDistinct(i)): count += 1 return count# Driver code L = 10R = 50print(findCount(L, R)) # This code is contributed# by saurabh_shukla |
C#
// C# implementation of the approach using System; class GFG { // Boolean function to check// distinct digits of a numberstatic Boolean checkDistinct(int x){ // Take last digit int last = x % 10; // Check if all other digits // are same as last digit while (x >0) { if (x % 10 != last) return false; // Remove last digit x = x / 10; } return true;} // Function to return the count of integers that// are composed of a single distinct digit onlystatic int findCount(int L, int R){ int count = 0; for (int i = L; i <= R; i++) { // If i has single distinct digit if (checkDistinct(i)) count += 1; } return count;} // Driver code static public void Main (String []args) { int L = 10, R = 50; Console.WriteLine (findCount(L, R)); } }//This code is contributed by Arnab Kundu. |
PHP
<?php// PHP implementation of the approach // Boolean function to check distinct// digits of a number function checkDistinct($x) { // Take last digit $last = $x % 10; // Check if all other digits // are same as last digit while ($x) { if ($x % 10 != $last) return false; // Remove last digit $x = floor($x / 10); } return true; } // Function to return the count of integers that // are composed of a single distinct digit only function findCount($L, $R) { $count = 0; for ($i = $L; $i <= $R; $i++) { // If i has single distinct digit if (checkDistinct($i)) $count += 1; } return $count; } // Driver code $L = 10;$R = 50; echo findCount($L, $R);// This code is contributed by Ryuga?> |
Javascript
<script>//javascript implementation of the approach // Boolean function to check // distinct digits of a number function checkDistinct(x) { // Take last digit var last = x % 10; // Check if all other digits // are same as last digit while (x > 0) { if (x % 10 != last) return false; // Remove last digit x = parseInt(x / 10); } return true; } // Function to return the count of integers that // are composed of a single distinct digit only function findCount(L , R) { var count = 0; for (i = L; i <= R; i++) { // If i has single distinct digit if (checkDistinct(i)) count += 1; } return count; } // Driver code var L = 10, R = 50; document.write(findCount(L, R));// This code contributed by aashish1995 </script> |
Output:
4
Time Complexity: O((R – L) * log10(R – L))
Auxiliary Space: O(1)
Efficient Approach:
- If L is a 2 digit number and R is a 5 digit number then all the 3 and 4 digit numbers of the form 111, 222, …, 999 and 1111, 2222, …, 9999 will be valid.
- So, count = count + (9 * (countDigits(R) – countDigits(L) – 1)).
- And, for the numbers which have equal number of digits as L, count all the valid numbers ? L.
- Similarly, for R count all the numbers ? R.
- If countDigits(L) = countDigits(R) then count the valid numbers ? L and exclude valid elements ? R.
- Print the count in the end.
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 count of digits of a numberint countDigits(int n){ int count = 0; while (n > 0) { count += 1; n /= 10; } return count;}// Function to return a number that contains only// digit 'd' repeated exactly count timesint getDistinct(int d, int count){ int num = 0; count = pow(10, count - 1); while (count > 0) { num += (count * d); count /= 10; } return num;}// Function to return the count of integers that// are composed of a single distinct digit onlyint findCount(int L, int R){ int count = 0; // Count of digits in L and R int countDigitsL = countDigits(L); int countDigitsR = countDigits(R); // First digits of L and R int firstDigitL = (L / pow(10, countDigitsL - 1)); int firstDigitR = (R / pow(10, countDigitsR - 1)); // If L has lesser number of digits than R if (countDigitsL < countDigitsR) { count += (9 * (countDigitsR - countDigitsL - 1)); // If the number that starts with firstDigitL and has // number of digits = countDigitsL is within the range // include the number if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); // Exclude the number else count += (9 - firstDigitL); // If the number that starts with firstDigitR and has // number of digits = countDigitsR is within the range // include the number if (getDistinct(firstDigitR, countDigitsR) <= R) count += firstDigitR; // Exclude the number else count += (firstDigitR - 1); } // If both L and R have equal number of digits else { // Include the number greater than L upto // the maximum number whose digit = coutDigitsL if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); else count += (9 - firstDigitL); // Exclude the numbers which are greater than R if (getDistinct(firstDigitR, countDigitsR) <= R) count -= (9 - firstDigitR); else count -= (9 - firstDigitR + 1); } // Return the count return count;}// Driver codeint main(){ int L = 10, R = 50; cout << findCount(L, R); return 0;} |
Java
// java implementation of the approachimport java.io.*;class GFG { // Function to return the count of digits of a numberstatic int countDigits(int n){ int count = 0; while (n > 0) { count += 1; n /= 10; } return count;}// Function to return a number that contains only// digit 'd' repeated exactly count timesstatic int getDistinct(int d, int count){ int num = 0; count = (int)Math.pow(10, count - 1); while (count > 0) { num += (count * d); count /= 10; } return num;}// Function to return the count of integers that// are composed of a single distinct digit onlystatic int findCount(int L, int R){ int count = 0; // Count of digits in L and R int countDigitsL = countDigits(L); int countDigitsR = countDigits(R); // First digits of L and R int firstDigitL = (L /(int)Math. pow(10, countDigitsL - 1)); int firstDigitR = (R / (int)Math.pow(10, countDigitsR - 1)); // If L has lesser number of digits than R if (countDigitsL < countDigitsR) { count += (9 * (countDigitsR - countDigitsL - 1)); // If the number that starts with firstDigitL and has // number of digits = countDigitsL is within the range // include the number if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); // Exclude the number else count += (9 - firstDigitL); // If the number that starts with firstDigitR and has // number of digits = countDigitsR is within the range // include the number if (getDistinct(firstDigitR, countDigitsR) <= R) count += firstDigitR; // Exclude the number else count += (firstDigitR - 1); } // If both L and R have equal number of digits else { // Include the number greater than L upto // the maximum number whose digit = coutDigitsL if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); else count += (9 - firstDigitL); // Exclude the numbers which are greater than R if (getDistinct(firstDigitR, countDigitsR) <= R) count -= (9 - firstDigitR); else count -= (9 - firstDigitR + 1); } // Return the count return count;}// Driver code public static void main (String[] args) { int L = 10, R = 50; System.out.println( findCount(L, R)); }}// This code is contributed by inder_verma. |
Python3
# Python3 implementation of the approach# Function to return the count # of digits of a numberdef countDigits(n): count = 0 while (n > 0): count += 1 n //= 10 return count# Function to return a number that contains only# digit 'd' repeated exactly count timesdef getDistinct(d, count): num = 0 count = pow(10, count - 1) while (count > 0): num += (count * d) count //= 10 return num# Function to return the count of integers that# are composed of a single distinct digit onlydef findCount(L, R): count = 0 # Count of digits in L and R countDigitsL = countDigits(L) countDigitsR = countDigits(R) # First digits of L and R firstDigitL = (L // pow(10, countDigitsL - 1)) firstDigitR = (R // pow(10, countDigitsR - 1)) # If L has lesser number of digits than R if (countDigitsL < countDigitsR): count += (9 * (countDigitsR - countDigitsL - 1)) # If the number that starts with firstDigitL # and has number of digits = countDigitsL is # within the range include the number if (getDistinct(firstDigitL, countDigitsL) >= L): count += (9 - firstDigitL + 1) # Exclude the number else: count += (9 - firstDigitL) # If the number that starts with firstDigitR # and has number of digits = countDigitsR is # within the range include the number if (getDistinct(firstDigitR, countDigitsR) <= R): count += firstDigitR # Exclude the number else: count += (firstDigitR - 1) # If both L and R have equal number of digits else: # Include the number greater than L upto # the maximum number whose digit = coutDigitsL if (getDistinct(firstDigitL, countDigitsL) >= L): count += (9 - firstDigitL + 1) else: count += (9 - firstDigitL) # Exclude the numbers which are greater than R if (getDistinct(firstDigitR, countDigitsR) <= R): count -= (9 - firstDigitR) else: count -= (9 - firstDigitR + 1) # Return the count return count# Driver codeL = 10R = 50print(findCount(L, R))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG {// Function to return the count // of digits of a numberstatic int countDigits(int n){ int count = 0; while (n > 0) { count += 1; n /= 10; } return count;}// Function to return a number that contains only// digit 'd' repeated exactly count timesstatic int getDistinct(int d, int count){ int num = 0; count = (int)Math.Pow(10, count - 1); while (count > 0) { num += (count * d); count /= 10; } return num;}// Function to return the count of integers that// are composed of a single distinct digit onlystatic int findCount(int L, int R){ int count = 0; // Count of digits in L and R int countDigitsL = countDigits(L); int countDigitsR = countDigits(R); // First digits of L and R int firstDigitL = (L / (int)Math.Pow(10, countDigitsL - 1)); int firstDigitR = (R / (int)Math.Pow(10, countDigitsR - 1)); // If L has lesser number of digits than R if (countDigitsL < countDigitsR) { count += (9 * (countDigitsR - countDigitsL - 1)); // If the number that starts with firstDigitL // and has number of digits = countDigitsL is // within the range include the number if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); // Exclude the number else count += (9 - firstDigitL); // If the number that starts with firstDigitR // and has number of digits = countDigitsR is // within the range include the number if (getDistinct(firstDigitR, countDigitsR) <= R) count += firstDigitR; // Exclude the number else count += (firstDigitR - 1); } // If both L and R have equal number of digits else { // Include the number greater than L upto // the maximum number whose digit = coutDigitsL if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); else count += (9 - firstDigitL); // Exclude the numbers which are // greater than R if (getDistinct(firstDigitR, countDigitsR) <= R) count -= (9 - firstDigitR); else count -= (9 - firstDigitR + 1); } // Return the count return count;}// Driver codepublic static void Main() { int L = 10, R = 50; Console.WriteLine(findCount(L, R));}}// This code is contributed // by Akanksha Rai |
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of digits of a number function countDigits(n) { let count = 0; while (n > 0) { count += 1; n = parseInt(n / 10, 10); } return count; } // Function to return a number that contains only // digit 'd' repeated exactly count times function getDistinct(d, count) { let num = 0; count = parseInt(Math.pow(10, count - 1), 10); while (count > 0) { num += (count * d); count = parseInt(count / 10, 10); } return num; } // Function to return the count of integers that // are composed of a single distinct digit only function findCount(L, R) { let count = 0; // Count of digits in L and R let countDigitsL = countDigits(L); let countDigitsR = countDigits(R); // First digits of L and R let firstDigitL = parseInt(L / parseInt(Math.pow(10, countDigitsL - 1), 10), 10); let firstDigitR = parseInt(R / parseInt(Math.pow(10, countDigitsR - 1), 10), 10); // If L has lesser number of digits than R if (countDigitsL < countDigitsR) { count += (9 * (countDigitsR - countDigitsL - 1)); // If the number that starts with firstDigitL // and has number of digits = countDigitsL is // within the range include the number if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); // Exclude the number else count += (9 - firstDigitL); // If the number that starts with firstDigitR // and has number of digits = countDigitsR is // within the range include the number if (getDistinct(firstDigitR, countDigitsR) <= R) count += firstDigitR; // Exclude the number else count += (firstDigitR - 1); } // If both L and R have equal number of digits else { // Include the number greater than L upto // the maximum number whose digit = coutDigitsL if (getDistinct(firstDigitL, countDigitsL) >= L) count += (9 - firstDigitL + 1); else count += (9 - firstDigitL); // Exclude the numbers which are // greater than R if (getDistinct(firstDigitR, countDigitsR) <= R) count -= (9 - firstDigitR); else count -= (9 - firstDigitR + 1); } // Return the count return count; } let L = 10, R = 50; document.write(findCount(L, R)); </script> |
Output:
4
Time Complexity: O(nlogn)
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!
