Create Sequence || POTD - Coding Ninjas

Problem Link :

https://www.codingninjas.com/studio/problems/create-sequence_920444?

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.

Constraints :

• 1 <= T <= 10

• 1 <= N <= 10^16

• Time Limit: 1 sec

Sample Input 1 :

2 (Number of TestCases)

10 (First Testcase)

100 (Second Testcase)

Sample Output 1 :

• 2 5

• 2 5 22 25 52 55

Explanation:

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.

BruteForce Approach :

Life goes on and on . . .🔁 Approach - Never Ending

def findNumbersInRange(start, end):
    result = []
    for num in range(start, end + 1):
        digits = set(str(num))
        if digits.issubset({'2', '5'}):
            result.append(num)
    return result

In this code, the findNumbersInRange the function takes the start and end values of the range as parameters. It initializes an empty list result to store the numbers that meet the criteria.

Then, it iterates over each number in the range using a for loop. For each number, it converts it to a string and creates a set digits containing its digits. It checks if the set of digits is a subset of the set {'2', '5'} using the issubset method. If all the digits are either 2 or 5, the number is added to the result list.

Finally, the function returns the list of numbers that consist only of the digits 2 and 5 in the given range.

We get the solution, But not in a convincing way... So we need an Optimized way

Optimized Approach 🤩 :

Exploring the Algorithm:

To begin our exploration, let's dive into the algorithm that uncovers these remarkable numbers. The code snippet provided below showcases a simple yet powerful approach to find all numbers composed solely of the digits 2 and 5 within a given range.

def findNumbersInRange(start, end):
    result = []
    queue = ['2', '5']  # Start with single-digit numbers 2 and 5

    while queue:
        num = queue.pop(0)
        if int(num) > end:
            break
        if int(num) >= start:
            result.append(int(num))

        queue.append(num + '2')  # Add next number by appending 2
        queue.append(num + '5')  # Add next number by appending 5

    return result

Let's dissect this algorithm step by step and understand its inner workings.

1. Initialization:

   • We start by initializing an empty result list to store the numbers we discover.

   • Additionally, we create a queue containing the initial single-digit numbers 2 and 5. This queue acts as our exploration frontier.

2. Exploration Loop:

   • The algorithm enters a loop that continues until the queue becomes empty.

   • In each iteration, we extract a number (num) from the front of the queue using the pop(0) operation.

3. Checking Range:

   • We compare the extracted number (num) with the given range boundaries (start and end).

   • If the number is greater than the end value, we break out of the loop, as we have explored the entire desired range.

   • If the number is within the range (num >= start), we add it to our result list.

4. Generating Next Numbers:

   • We expand our exploration by generating the next set of numbers from the current number (num).

   • To do this, we append two new numbers to the queue:

     • By appending '2' to num, we create a new number that includes '2' as its rightmost digit.

     • By appending '5' to num, we create a new number that includes '5' as its rightmost digit.

   • These newly generated numbers will be explored in subsequent iterations, allowing us to uncover more numbers in our range.

5. Return the Result:

   • Once the exploration loop concludes, we return the result list containing all the discovered numbers.

Example Run:

Let's consider an example to illustrate the algorithm in action. Suppose we want to find all numbers composed solely of the digits 2 and 5 in the range from 10 to 100.

Using the findNumbersInRange(start, end) function with start = 10 and end = 100, we obtain the following result:

[22, 25, 52, 55]

Conclusion:

In this article, we embarked on an enthralling journey to explore numbers composed solely of the digits 2 and 5. By employing a clever algorithm, we uncovered a fascinating collection of these special numbers within a specific range. The provided code snippet served as our guide, demonstrating how simple yet powerful techniques can unlock intriguing numerical patterns.

If you find this topic as captivating as we do, we invite you to follow our page for daily articles on optimal solutions, beautiful explanations, and further exploration into the realm of mathematical wonders.

Together, let's unveil the secrets hidden within the numbers composed of 2 and 5!

Happy coding ✨