Sequential Digits

Moderate

0/80

0 upvote

Asked in company

Problem statement

An integer is said to have sequential digits if and only if each digit in the number is one greater than the preceding digit. For example, the numbers 123, 4567, and 89 all have sequential digits.

You are given an inclusive integer range [low, high]. Your task is to find all integers within this range that have sequential digits and return them as a sorted list.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains two space-separated integers, low and high.

Output Format:

Print a single line containing all the sequential-digit integers in the range [low, high], sorted in ascending order and separated by spaces.

If no such integers exist in the range, print an empty line.

Note:

The number of integers with sequential digits is very small. A highly efficient approach is to generate all possible sequential-digit numbers first and then filter them based on whether they fall within the given range [low, high].

Sample Input 1:

100 300

Sample Output 1:

123 234

Explanation for Sample 1:

The sequential-digit numbers are generated: 12, 23, 34, ..., 89, 123, 234, 345, ...
From this list, only 123 and 234 fall within the inclusive range [100, 300].

Sample Input 2:

1000 13000

Sample Output 2:

1234 2345 3456 4567 5678 6789 12345

Explanation for Sample 2:

All sequential-digit integers with 4 and 5 digits are generated. Those that fall within the range [1000, 13000] are collected and returned in a sorted list.

Expected Time Complexity:

The expected time complexity is O(N^2).

Constraints:

1 <= low <= high <= 10^9

Time Limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Sequential Digits

Console