Given a positive number n, print a number less than n such that all its digits are distinct.
Examples:
Input : 1134 Output : 1098 1098 is the largest number smaller than 1134 such that all digits are distinct. Input : 4559 Output : 4539
The problem can easily be solved by using counting. Firstly, loop through numbers less than n and for each number count the frequency of the digits using count array. If all the digits occur only once than we print that number. The answer always exists so there is no problem of infinite loop.
C++
// CPP program to find a number less than// n such that all its digits are distinct#include <bits/stdc++.h>using namespace std;// Function to find a number less than// n such that all its digits are distinctint findNumber(int n){ // looping through numbers less than n for (int i = n - 1; >=0 ; i--) { // initializing a hash array int count[10] = { 0 }; int x = i; // creating a copy of i // initializing variables to compare lengths of digits int count1 = 0, count2 = 0; // counting frequency of the digits while (x) { count[x % 10]++; x /= 10; count1++; } // checking if each digit is present once for (int j = 0; j < 10; j++) { if (count[j] == 1) count2++; } if (count1 == count2) return i; }}// Driver codeint main(){ int n = 8490; cout << findNumber(n); return 0;} |
Java
// Java program to find a number less than// n such that all its digits are distinctclass GFG{// Function to find a number less than// n such that all its digits are distinctstatic int findNumber(int n){ // looping through numbers less than n for (int i = n - 1;i >=0 ; i--) { // initializing a hash array int[] count=new int[10]; int x = i; // creating a copy of i // initializing variables to compare lengths of digits int count1 = 0, count2 = 0; // counting frequency of the digits while (x>0) { count[x % 10]++; x /= 10; count1++; } // checking if each digit is present once for (int j = 0; j < 10; j++) { if (count[j] == 1) count2++; } if (count1 == count2) return i; } return -1;}// Driver codepublic static void main(String[] args){ int n = 8490; System.out.println(findNumber(n));}}// This code is contributed by mits |
Python3
# python 3 program to find a number less than# n such that all its digits are distinct# Function to find a number less than# n such that all its digits are distinctdef findNumber(n): # looping through numbers less than n i = n-1 while(i>=0): # initializing a hash array count = [0 for i in range(10)] x = i # creating a copy of i # initializing variables to compare lengths of digits count1 = 0 count2 = 0 # counting frequency of the digits while (x): count[x%10] += 1 x = int(x / 10) count1 += 1 # checking if each digit is present once for j in range(0,10,1): if (count[j] == 1): count2 += 1 if (count1 == count2): return i i -= 1 # Driver codeif __name__ == '__main__': n = 8490 print(findNumber(n))# This code is implemented by# Surendra_Gangwar |
C#
// C# program to find a number less than// n such that all its digits are distinctusing System;class GFG{ // Function to find a number less than// n such that all its digits are distinctstatic int findNumber(int n){ // looping through numbers less than n for (int i = n - 1; i >= 0; i--) { // initializing a hash array int[] count = new int[10]; int x = i; // creating a copy of i // initializing variables to compare // lengths of digits int count1 = 0, count2 = 0; // counting frequency of the digits while (x > 0) { count[x % 10]++; x /= 10; count1++; } // checking if each digit is // present once for (int j = 0; j < 10; j++) { if (count[j] == 1) count2++; } if (count1 == count2) return i; } return -1;}// Driver codestatic public void Main (){ int n = 8490; Console.WriteLine(findNumber(n));}}// This code is contributed by akt_mit |
PHP
<?php// PHP program to find a number less than// n such that all its digits are distinct// Function to find a number less than// n such that all its digits are distinctfunction findNumber($n){ // looping through numbers less than n for ($i = $n - 1;$i >= 0 ; $i--) { // initializing a hash array $count = array_fill(0, 10, 0); $x = $i; // creating a copy of i // initializing variables to // compare lengths of digits $count1 = 0; $count2 = 0; // counting frequency of the digits while ($x) { $count[$x % 10]++; $x = (int)($x / 10); $count1++; } // checking if each digit // is present once for ($j = 0; $j < 10; $j++) { if ($count[$j] == 1) $count2++; } if ($count1 == $count2) return $i; }}// Driver code$n = 8490;echo findNumber($n);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript program to find a number less than// n such that all its digits are distinct// Function to find a number less than// n such that all its digits are distinctfunction findNumber(n){ // looping through numbers less than n for (i = n - 1;i >=0 ; i--) { // initializing a hash array var count=Array.from({length: 10}, (_, i) => 0); var x = i; // creating a copy of i // initializing variables to compare lengths of digits var count1 = 0, count2 = 0; // counting frequency of the digits while (x>0) { count[x % 10]++; x = parseInt(x/10); count1++; } // checking if each digit is present once for (j = 0; j < 10; j++) { if (count[j] == 1) count2++; } if (count1 == count2) return i; } return -1;}// Driver codevar n = 8490;document.write(findNumber(n));// This code is contributed by 29AjayKumar </script> |
Output:
8479
Time Complexity: O(N*log10N) where n is number of elements in given array. As, we are using a loop to traverse N times so it will cost us O(N) time and we are using a while loop which will cost O (logN) as we are decrement by floor division of 10 each time.
Auxiliary Space: O(1), as we are not using any extra space.
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!
