Given an array arr[] of size 10 where arr[i] represents the frequency of the digit i. The task is to find the smallest positive number which can not be represented by the given digits.
Examples:
Input: arr[] = {2, 1, 1, 4, 0, 6, 3, 2, 2, 2}
Output: 4
Since the count of 4th digit is 0. So 4 can not be made.Input : arr[] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output : 10
Since the count of 0th digit is 0. So smallest positive integer that can not be made is 10.Input : arr[] = {2, 2, 1, 2, 1, 1, 3, 1, 1, 1}
Output : 22
To make 22 we require two 2’s but here the count of 2 is only 1.
Approach: The idea to solve the problem is to
Find the minimum index having the minimum value and form the number with that index.
Follow the steps mentioned below to implement the idea:
- Calculate the min value in the array starting from 1st index and also store its index.
- Now compare the min value with the value at 0th index.
- If the value at 0th index is less than the min value then either 10, 100, 1000 . . . can’t be expressed.
- If the value 0th index is greater than min value then:
- The resultant number will have the index of min value total (min value + 1) times.
- So print that index (min value + 1) times to get the answer.
Below is the implementation of the above approach:
C++
// CPP program to find the smallest positive// number which can not be represented by given digits#include <bits/stdc++.h>using namespace std;// Function to find the smallest positive// number which can not be represented by given digitsvoid expressDigit(int arr[], int n){ int min = 1000000000, index = 0, temp = 0; // Storing the count of 0 digit // or store the value at 0th index temp = arr[0]; // Calculates the min value in the array starting // from 1st index and also store it index. for (int i = 1; i < 10; i++) { if (arr[i] < min) { min = arr[i]; index = i; } } // Now compare the min value with the // value at 0th index. // If its value at 0th index is less than min value // than either 10, 100, 1000 ... can't be expressed if (temp < min) { cout << 1; for (int i = 1; i <= temp + 1; i++) cout << 0; } // If it value is greater than min value than // iterate the loop upto first min value index // and simply print it index value. else { for (int i = 0; i < min; i++) cout << index; cout << index; }}// Driver codeint main(){ int arr[] = { 2, 2, 1, 2, 1, 1, 3, 1, 1, 1 }; // Value of N is always 10 as we take digit from 0 to 9 int N = 10; // Calling function expressDigit(arr, N); return 0;} |
Java
// Java program to find the smallest positive// number which can not be represented by given digitsimport java.util.*;class GFG { // Function to find the smallest positive // number which can not be represented by given digits static void expressDigit(int arr[], int n) { int min = 1000000000, index = 0, temp = 0; // Storing the count of 0 digit // or store the value at 0th index temp = arr[0]; // Calculates the min value in the array starting // from 1st index and also store it index. for (int i = 1; i < 10; i++) { if (arr[i] < min) { min = arr[i]; index = i; } } // Now compare the min value with the // value at 0th index. // If its value at 0th index is less than min value // than either 10, 100, 1000 ... can't be expressed if (temp < min) { System.out.print(1); for (int i = 1; i <= temp + 1; i++) System.out.print(0); } // If it value is greater than min value than // iterate the loop upto first min value index // and simply print it index value. else { for (int i = 0; i < min; i++) System.out.print(index); System.out.print(index); } } // Driver code public static void main(String[] args) { int arr[] = { 2, 2, 1, 2, 1, 1, 3, 1, 1, 1 }; // Value of N is always 10 // as we take digit from 0 to 9 int N = 10; // Calling function expressDigit(arr, N); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the# smallest positive number which# can not be represented by given digits# Function to find the smallest# positive number which can not be# represented by given digitsdef expressDigit(arr, n): min = 1000000000 index = 0 temp = 0 # Storing the count of 0 digit # or store the value at 0th index temp = arr[0] # Calculates the min value in # the array starting from # 1st index and also store its index. for i in range(1, 10): if(arr[i] < min): min = arr[i] index = i # Now compare the min value with the # value at 0th index. # If its value at 0th index is # less than min value than either # 10, 100, 1000 ... can't be expressed if(temp < min): print(1, end="") for i in range(1, temp + 1): print(0, end="") # If its value is greater than # min value then iterate the loop # upto first min value index and # simply print its index value. else: for i in range(min): print(index, end="") print(index)# Driver codearr = [2, 2, 1, 2, 1, 1, 3, 1, 1, 1]# Value of N is always 10# as we take digit from 0 to 9N = 10# Calling functionexpressDigit(arr, N)# This code is contributed by Mohit Kumar |
C#
// C# program to find the smallest positive// number which can not be represented by given digitsusing System;class GFG { // Function to find the smallest positive // number which can not be represented by given digits static void expressDigit(int[] arr, int n) { int min = 1000000000, index = 0, temp = 0; // Storing the count of 0 digit // or store the value at 0th index temp = arr[0]; // Calculates the min value in the array starting // from 1st index and also store it index. for (int i = 1; i < 10; i++) { if (arr[i] < min) { min = arr[i]; index = i; } } // Now compare the min value with the // value at 0th index. // If its value at 0th index is less than min value // than either 10, 100, 1000 ... can't be expressed if (temp < min) { Console.Write(1); for (int i = 1; i <= temp + 1; i++) Console.Write(0); } // If it value is greater than min value than // iterate the loop upto first min value index // and simply print it index value. else { for (int i = 0; i < min; i++) Console.Write(index); Console.Write(index); } } // Driver code public static void Main(String[] args) { int[] arr = { 2, 2, 1, 2, 1, 1, 3, 1, 1, 1 }; // Value of N is always 10 // as we take digit from 0 to 9 int N = 10; // Calling function expressDigit(arr, N); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program to find the smallest positive // number which can not be represented by given digits // Function to find the smallest positive // number which can not be represented by given digits function expressDigit(arr, n) { var min = 1000000000, index = 0, temp = 0; // Storing the count of 0 digit // or store the value at 0th index temp = arr[0]; // Calculates the min value in the array starting // from 1st index and also store it index. for (i = 1; i < 10; i++) { if (arr[i] < min) { min = arr[i]; index = i; } } // Now compare the min value with the // value at 0th index. // If its value at 0th index is less than min value // than either 10, 100, 1000 ... can't be expressed if (temp < min) { document.write(1); for (i = 1; i <= temp + 1; i++) document.write(0); } // If it value is greater than min value than // iterate the loop upto first min value index // and simply print it index value. else { for (i = 0; i < min; i++) document.write(index); document.write(index); } } // Driver code var arr = [ 2, 2, 1, 2, 1, 1, 3, 1, 1, 1 ]; // Value of N is always 10 // as we take digit from 0 to 9 var N = 10; // Calling function expressDigit(arr, N);// This code is contributed by gauravrajput1 </script> |
Output
22
Time Complexity: O(min(A[i])), where min(A[i]) is the minimum element in the given array
Auxiliary Space: O(1), as constant extra space is required.
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!
