Create Sequence

Easy
0/40
Average time to solve is 10m
profile
Contributed by
60 upvotes
Asked in company
IBM

Problem statement

Ninja is good at numbers. So today his friend gave him a task that required him to find out numbers made of 2 and 5 only less than a given limit.

Given an integer N, you need to print all numbers less than N which are having digits only 2 or 5 or both.

For example : 
All numbers less than 30 with digits 2 and 5 are 2, 5, 22, 25.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer N representing the number in the problem statement.
Output format : 
For each test case, print all the numbers less than N consisting of digits 2 and 5 only in a space-separated format. The numbers should be printed in ascending order.

Output for each test case will be printed in a separate line.
Constraints : 
1 <= T <= 10
1 <= N <= 10^16

Time Limit: 1 sec
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.

Sample Input 1 :

2  
10
100

Sample Output 1 :

2 5 
2 5 22 25 52 55
Explanation For Sample Output 1 :
For the first test case, only 2 and 5 are the required numbers. Hence we print them in ascending order.
For the second test case, we have 6 required numbers.
Sample Input 2 :
2
2
7
Sample Output 2 :
2
2 5
Hint

How can you generate all possible numbers using 2 and 5 using recursion?

Approaches (1)
Generate all possible numbers

We can consider a number with digits 2 and 5 as a binary string where 0 represents a 2 in the number and 1 represents the 5. This way our total numbers consisting of 2 and 5 are limited by 2^(D + 1) where D is the total number of digits in the input number N.

 

So we define a recursive function that takes a current number of length D and either appends a 2 or 5 to the end of this number. 

 

Algorithm:

 

print(num, result) function takes the current number num and the result array ‘result’ and appends the numbers satisfying the above criteria to the result array.

  • If the number becomes greater than N we return as a base case.
  • we append the number to the current list.
  • We recursively call the print function by appending a 2 and a 5 at the end.


 

Time Complexity

O(2^D)  Where D is the number of digits of N.


For every number less than N we have 2 choices, either append 2 or 5. Hence the overall complexity becomes O(2^D)

Space Complexity

O(D) Where D is the number of digits of N.

 

D is the maximum length of stack size possible in the recursion stack. 

Code Solution
(100% EXP penalty)
Create Sequence
Full screen
Console