[Solved] Create Sequence Contest Problem

Create Sequence: 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.

Create Sequence Contest Problem

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

Solution

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. 

Solution

/*
    Time Complexity: O( 2^D ).
    Space Complexity: O( D ).

    Where D is the number of digits in the input.
*/

import java.util.ArrayList;
import java.util.Collections;

// Recursive function to add the numbers to the result.
public class Solution {
   static void createSequenceHelper(long  current, long  n, ArrayList<Long> result){

        // Base case.
        if(current > n) {
            return ;
        }

        // Add the current number to result.
        if(current != 0) {
            result.add(current);
        }

        // Recurse by adding 2 and 5 to the end of the number
        createSequenceHelper(current * 10  + 2, n, result);
        createSequenceHelper(current * 10 + 5, n, result);
    }

    public static ArrayList<Long> createSequence(long n){

        // List to store the numbers in increasing order.
        ArrayList<Long> result =new ArrayList<>();

        // Call the function to add numbers to the result.
        createSequenceHelper(0, n, result);
        Collections.sort(result);

        // Return result.
        return result;
    }
}

/*
    Time Complexity: O( 2^D ).
    Space Complexity: O( D ).

    Where D is the number of digits in the input
*/

/*
    Recursive function to add the numbers to the result.
*/
void createSequenceHelper(long long current, long long n, vector<long long> &result){
    
    // Base case.
    if(current > n) {
        return ;
    }
        

    // Add the current number to result.
    if(current != 0) {
        result.push_back(current);
    }

    // Recurse by adding 2 and 5 to the end of the number
    createSequenceHelper(current * 10  + 2, n, result);
    createSequenceHelper(current * 10 + 5, n, result);
}
vector<long long> createSequence(long long n) {

    // Vector to store the numbers in increasing order.
    vector<long long> result;

    // Call the function to add numbers to the result.  
    createSequenceHelper(0, n, result);
    sort(result.begin(), result.end());
    // Return result.
    return result;

}

'''
    Time Complexity: O( 2^D ).
    Space Complexity: O( D ).

    Where D is the number of digits in the input.
'''

def createSequenceHelper(current, n, result):
    
    # Base case.
    if current > n:
        return
    
    # Add the current number to result.
    if current != 0:
        result.append(current)
        
    # Recurse by adding 2 and 5 to the end of the number.
    createSequenceHelper(current * 10  + 2, n, result)
    createSequenceHelper(current * 10 + 5, n, result)
    
def createSequence(n):
    
    # List to store the numbers in increasing order.
    result = []
    
    # Call the function to add numbers to the result.
    createSequenceHelper(0, n, result)
    
    result = sorted(result)
    
    # Return result.
    return result

Happy Learning – If you require any further information, feel free to contact me.