Find Numbers Containing 1, 2, and 3

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in company
Goldman Sachs

Problem statement

You’re given an array of ‘N’ integers. Your task is to find all those array elements which contain 1, 2, and 3 in their digits and then print them in ascending order. If no element has 1,2 and 3 in its digits, then print ‘-1’.

Example : 
12345 satisfies the condition since it has all ‘1’, ‘2’, and ‘3’ in its digits, but 124 doesn’t satisfy the condition since it only has ‘1’ and ‘2’ but not ‘3’ in its digits.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains an integer N, the number of elements in the array.

The next line of each test case contains N space-separated integers, denoting the array elements.
Output Format : 
For every test case, the only output line contains an array containing the elements with ‘1’,’2’, and ‘3’ in their digits in ascending order.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Note: 
You have to return an array containing elements with ‘1’,’2’, and ‘3’ in their digits in ascending order. If there is no such element containing ‘1’, ‘2’, and ‘3’ in its digits, return an empty array.
Constraints : 
1 <= T <= 5
1 <=  N <= 10^5
1 <= arr[i] <= 10^9    

Time limit: 1 sec
Sample Input 1 :
1 
5
123 1234 12345 1245 1230
Sample Output 1 :
123 1230 1234 12345
Explanation For Sample Input 1 :
Out of the given array elements, only 1245 doesn’t have the digit ‘3’. Hence we’ll print all other elements in ascending order.
Sample Input 2 :
2
4
321 123 131 432
3
124 324 134
Sample Output 2 :
123 321
-1
Hint

Check if the elements contain the digits.

Approaches (1)
Implementation Based

We will create an “answer” array to store the elements with ‘1’, ‘2’, and ‘3’ in their digits. For all the array elements, we will check if the element contains ‘1’, ‘2’, and ‘3’, and if this condition is true, then we will push this element into our answer array.

 

Algorithm :

 

  • Create a boolean helper function containsNumberHelper() to check if the array element(arr[i]) contains ‘1’, ‘2’, and ‘3’.
    • Make three bool variables “one,” “two,” and “three,” and initialize them as false.
    • For each element arr[i], check if the last digit of arr[i] equals 1, 2, and 3 and update “one,” “two,” and “three” accordingly. If it is equal to 1, then update “one” = true. Similarly, do this for “two” and “three.”
    • Then shift to the next digit and repeat step b. We will do this for all the digits of arr[i]. To optimize further, we will break and won’t go to the next digit once we have encountered all the three digits, i.e., ‘1’, ‘2’, and ‘3’.
    • Return( one && two && three). This will return true only when all “one,” “two,” and “three” are true, indicating that the current array element contains 1,2 and 3 in its digits.
  • Inside our containsNumber() function, make an array “answer” and run a loop(loop variable i) from 0 till N -1.
    • For each arr[i], check if containsNumberHelper(arr[i]) = true or not. If it’s true, then push arr[i] into our “answer” array.
  • Finally, sort this “answer” array and then return it.
Time Complexity

O(N * log(N)), where ‘N’ is the number of elements in the array.

 

We are traversing an array of N elements that will take O(N) time, and containsNumberHelper() will take constant time. Also, we will be sorting the ‘answer’ array which will take O(N * log(N)) time.  Hence, the final time complexity will be O(N) + O(N * log(N))= O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the number of elements in the array.

 

As we are making an answer array of size ‘N.’ Hence, the final space complexity will be O(N).

Code Solution
(100% EXP penalty)
Find Numbers Containing 1, 2, and 3
Full screen
Console