Given a non-negative number n and a value k. Find the kth smallest number that can be formed using the digits of the given number n. It is guaranteed that the kth smallest number can be formed. Note that the number could be very large and may not even fit into long long int. Examples:
Input : n = 1234, k = 2 Output : 1243 Input : n = 36012679802, k = 4 Output : 10022366897
The idea is to first sort digits and find the smallest number, then find k-th permutation starting from smallest number. To sort digits, we use an frequency counting technique as number of digits are small.
CPP
// C++ implementation to get the kth smallest // number using the digits of the given number #include <bits/stdc++.h> using namespace std; // function to get the smallest digit in 'num' // which is greater than 0 char getSmallDgtGreaterThanZero(string num, int n) { // 's_dgt' to store the smallest digit // greater than 0 char s_dgt = '9'; for (int i=0; i<n; i++) if (num[i] < s_dgt && num[i] != '0') s_dgt = num[i]; // required smallest digit in 'num' return s_dgt; } // function to get the kth smallest number string kthSmallestNumber(string num, int k) { // FIND SMALLEST POSSIBLE NUMBER BY SORTING // DIGITS // count frequency of each digit int freq[10]; string final_num = ""; memset(freq, 0, sizeof(freq)); int n = num.size(); // counting frequency of each digit for (int i = 0; i < n; i++) freq[num[i] - '0']++; // get the smallest digit greater than 0 char s_dgt = getSmallDgtGreaterThanZero(num, n); // add 's_dgt' to 'final_num' final_num += s_dgt; // reduce frequency of 's_dgt' by 1 in 'freq' freq[s_dgt - '0']--; // add each digit according to its frequency // to 'final_num' for (int i=0; i<10; i++) for (int j=1; j<=freq[i]; j++) final_num += (char)(i+48); // FIND K-TH PERMUTATION OF SMALLEST NUMBER for (int i=1; i<k; i++) next_permutation(final_num.begin(), final_num.end()); // required kth smallest number return final_num; } // Driver program to test above int main() { string num = "36012679802"; int k = 4; cout << kthSmallestNumber(num, k); return 0; } |
Java
// GFG// Java program that finds the kth smallest number using the// digits of a given numberimport java.util.*;class Main { // function to get the smallest digit in 'num' // which is greater than 0 static char getSmallDgtGreaterThanZero(String num, int n) { // 's_dgt' to store the smallest digit // greater than 0 char s_dgt = '9'; for (int i = 0; i < n; i++) { if (num.charAt(i) < s_dgt && num.charAt(i) != '0') { s_dgt = num.charAt(i); } } // required smallest digit in 'num' return s_dgt; } // function to get the kth smallest number static String kthSmallestNumber(String num, int k) { // FIND SMALLEST POSSIBLE NUMBER BY SORTING // DIGITS // count frequency of each digit int[] freq = new int[10]; StringBuilder final_num = new StringBuilder(); Arrays.fill(freq, 0); int n = num.length(); // counting frequency of each digit for (int i = 0; i < n; i++) { freq[num.charAt(i) - '0']++; } // get the smallest digit greater than 0 char s_dgt = getSmallDgtGreaterThanZero(num, n); // add 's_dgt' to 'final_num' final_num.append(s_dgt); // reduce frequency of 's_dgt' by 1 in 'freq' freq[s_dgt - '0']--; // add each digit according to its frequency // to 'final_num' for (int i = 0; i < 10; i++) { for (int j = 1; j <= freq[i]; j++) { final_num.append((char)(i + '0')); } } // FIND K-TH PERMUTATION OF SMALLEST NUMBER for (int i = 1; i < k; i++) { String temp = final_num.toString(); final_num = new StringBuilder(); final_num.append(nextPermutation(temp)); } // required kth smallest number return final_num.toString(); } // function to find the next permutation of a given // string static String nextPermutation(String str) { char[] arr = str.toCharArray(); int i = arr.length - 2; // find the rightmost element that is smaller than // its next element while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } // if no such element is found, the string is // already the last permutation if (i < 0) { return str; } // find the smallest element to the right of the // element found above that is greater than it int j = arr.length - 1; while (j > i && arr[j] <= arr[i]) { j--; } // swap the two elements char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // reverse the substring to the right of the first // element found above int left = i + 1; int right = arr.length - 1; while (left < right) { temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } // requires kth smallest number return new String(arr); } // driver code to test above public static void main(String[] args) { String num = "36012679802"; int k = 4; System.out.println(kthSmallestNumber(num, k)); }}// This code is contributed by Sundaram. |
Python3
# Python Codedef getSmallDgtGreaterThanZero(num, n): # 's_dgt' to store the smallest digit # greater than 0 s_dgt = '9' for i in range(0, n): if (num[i] < s_dgt and num[i] != '0'): s_dgt = num[i] # required smallest digit in 'num' return s_dgt # function to get the kth smallest number def kthSmallestNumber(num, k): # FIND SMALLEST POSSIBLE NUMBER BY SORTING # DIGITS # count frequency of each digit freq = [0] * 10 final_num = "" # counting frequency of each digit for i in range(0, len(num)): freq[int(num[i])] += 1 # get the smallest digit greater than 0 s_dgt = getSmallDgtGreaterThanZero(num, len(num)) # add 's_dgt' to 'final_num' final_num += s_dgt # reduce frequency of 's_dgt' by 1 in 'freq' freq[int(s_dgt)] -= 1 # add each digit according to its frequency # to 'final_num' for i in range(0, 10): for j in range(1, freq[i] + 1): final_num += str(i) # FIND K-TH PERMUTATION OF SMALLEST NUMBER for i in range(1, k): temp = final_num final_num = "" final_num += nextPermutation(temp) # required kth smallest number return final_num # function to find the next permutation of a given # string def nextPermutation(str): arr = list(str) i = len(arr) - 2 # find the rightmost element that is smaller than # its next element while (i >= 0 and arr[i] >= arr[i + 1]): i -= 1 # if no such element is found, the string is # already the last permutation if (i < 0): return str # find the smallest element to the right of the # element found above that is greater than it j = len(arr) - 1 while (j > i and arr[j] <= arr[i]): j -= 1 # swap the two elements arr[i], arr[j] = arr[j], arr[i] # reverse the substring to the right of the first # element found above left = i + 1 right = len(arr) - 1 while (left < right): arr[left], arr[right] = arr[right], arr[left] left += 1 right -= 1 # requires kth smallest number return "".join(arr) # driver code to test above num = "36012679802"k = 4print(kthSmallestNumber(num, k)) |
C#
// C# implementation to get the kth smallest // number using the digits of the given number using System;using System.Linq;using System.Text;class MainClass { // function to get the smallest digit in 'num' // which is greater than 0 public static char GetSmallDgtGreaterThanZero(string num, int n) { // 's_dgt' to store the smallest digit // greater than 0 char s_dgt = '9'; for (int i = 0; i < n; i++) { if (num[i] < s_dgt && num[i] != '0') { s_dgt = num[i]; } } // required smallest digit in 'num' return s_dgt; } // function to get the kth smallest number public static string KthSmallestNumber(string num, int k) { // FIND SMALLEST POSSIBLE NUMBER BY SORTING // DIGITS // count frequency of each digit int[] freq = new int[10]; StringBuilder final_num = new StringBuilder(); Array.Fill(freq, 0); int n = num.Length; // counting frequency of each digit for (int i = 0; i < n; i++) { freq[num[i] - '0']++; } // get the smallest digit greater than 0 char s_dgt = GetSmallDgtGreaterThanZero(num, n); // add 's_dgt' to 'final_num' final_num.Append(s_dgt); // reduce frequency of 's_dgt' by 1 in 'freq' freq[s_dgt - '0']--; // add each digit according to its frequency // to 'final_num' for (int i = 0; i < 10; i++) { for (int j = 1; j <= freq[i]; j++) { final_num.Append((char)(i + '0')); } } // FIND K-TH PERMUTATION OF SMALLEST NUMBER for (int i = 1; i < k; i++) { string temp = final_num.ToString(); final_num = new StringBuilder(); final_num.Append(NextPermutation(temp)); } // required kth smallest number return final_num.ToString(); } // function to find the next permutation of a given // string public static string NextPermutation(string str) { char[] arr = str.ToCharArray(); int i = arr.Length - 2; // find the rightmost element that is smaller than // its next element while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } // if no such element is found, the string is // already the last permutation if (i < 0) { return str; } // find the smallest element to the right of the // element found above that is greater than it int j = arr.Length - 1; while (j > i && arr[j] <= arr[i]) { j--; } // swap the two elements char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // reverse the substring to the right of the first // element found above int left = i + 1; int right = arr.Length - 1; while (left < right) { temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } // requires kth smallest number return new String(arr); } // driver code to test above static void Main() { string num = "36012679802"; int k = 4; Console.WriteLine(KthSmallestNumber(num, k)); }}// This code is contributed by Arushi Goel. |
Javascript
// JavaScript Codefunction getSmallDgtGreaterThanZero(num, n) { // 's_dgt' to store the smallest digit // greater than 0 let s_dgt = '9'; for (let i = 0; i < n; i++) { if (num[i] < s_dgt && num[i] !== '0') { s_dgt = num[i]; } } // required smallest digit in 'num' return s_dgt;}// function to get the kth smallest numberfunction kthSmallestNumber(num, k) { // FIND SMALLEST POSSIBLE NUMBER BY SORTING // DIGITS // count frequency of each digit const freq = new Array(10).fill(0); let final_num = ''; // counting frequency of each digit for (let i = 0; i < num.length; i++) { freq[parseInt(num[i])] += 1; } // get the smallest digit greater than 0 const s_dgt = getSmallDgtGreaterThanZero(num, num.length); // add 's_dgt' to 'final_num' final_num += s_dgt; // reduce frequency of 's_dgt' by 1 in 'freq' freq[parseInt(s_dgt)] -= 1; // add each digit according to its frequency // to 'final_num' for (let i = 0; i < 10; i++) { for (let j = 1; j <= freq[i]; j++) { final_num += i.toString(); } } // FIND K-TH PERMUTATION OF SMALLEST NUMBER for (let i = 1; i < k; i++) { let temp = final_num; final_num = ''; final_num += nextPermutation(temp); } // required kth smallest number return final_num;}// function to find the next permutation of a given// stringfunction nextPermutation(str) { let arr = str.split(''); let i = arr.length - 2; // find the rightmost element that is smaller than // its next element while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } // if no such element is found, the string is // already the last permutation if (i < 0) { return str; } // find the smallest element to the right of the // element found above that is greater than it let j = arr.length - 1; while (j > i && arr[j] <= arr[i]) { j--; } // swap the two elements [arr[i], arr[j]] = [arr[j], arr[i]]; // reverse the substring to the right of the first // element found above let left = i + 1; let right = arr.length - 1; while (left < right) { [arr[left], arr[right]] = [arr[right], arr[left]]; left++; right--; } // requires kth smallest number return arr.join('');}// driver code to test abovelet num = '36012679802';let k = 4;console.log(kthSmallestNumber(num, k)); |
Output
10022366897
Time Complexity: O(n)
Auxiliary Space: O(1)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
