Find Numbers Containing 1, 2, and 3

Posted: 25 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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.
Try Problem