Sequential Digits

Problem Statement

In the given problem, we are required to identify all integers whose digits are sequential increments within a specified range defined by two numbers, low and high. An integer is described as having sequential digits if every digit in the number is exactly one more than the preceding digit. The objective is to produce a sorted list of all such integers that lie within the inclusive range from low to high.

Examples

Example 1

Input:

low = 100, high = 300

Output:

[123,234]

Example 2

Input:

low = 1000, high = 13000

Output:

[1234,2345,3456,4567,5678,6789,12345]

Constraints

• 10 <= low <= high <= 10^9

Approach and Intuition

To solve this problem of finding integers with sequential digits within a specific range, we can employ a straightforward approach:

Understanding Sequential Digits: Sequential digits follow a pattern such as 123, 234, 1234, wherein each digit is one greater than the previous. Notably, the length of these sequential numbers can range from 2 to 9 digits.

Generating Sequential Digits:

1. We shall start by generating the smallest sequential numbers for each possible length. For instance, for two digits, the number is 12; for three, it's 123, and so forth until 123456789.
2. Increment sequential numbers. For example, from 12, the next is 23, 34, up to 89. This is done by examining and shifting the digits of the number accordingly.

Filtering based on Range: Once we have a list of all possible sequential digits:

1. We simply filter out the numbers that do not fall within the low to high range.
2. The range constraint dictates that every sequential digit number falling outside this range is not included in the result.

Optimizations and Considerations:

• Utilize the constraints provided (10 <= low <= high <= 10^9). This helps in reducing unnecessary computations, especially dealing with the upper bounds of digits available in the numbers.
• By observing the upper limit, we should consider that numbers like 123456789 are viable but 1234567890 is not due to the increase in the sequential pattern.
• Ensure that our list is sorted as required. Naturally, the generation of numbers methodically from smallest to the largest digit count should inherently keep it sorted.
• Handle edge cases diligently, such as when low and high encapsulate very few digits, or are very close in value limiting the number of results substantially.

Through this method, we efficiently generate the required numbers without generating extraneous ones, thus optimizing our approach, especially given the vast range limits.

Solutions

class Sequence {
  public List<Integer> sequenceList = new ArrayList<>();
  Sequence() {
    String digits = "123456789";
    int limit = 10;
    
    for (int len = 2; len < limit; ++len) {
      for (int start = 0; start < limit - len; ++start) {
        int number = Integer.parseInt(digits.substring(start, start + len));
        sequenceList.add(number);
      }
    }
  }
}
    
class Solution {
  public static Sequence seq = new Sequence();
  public List<Integer> getSequentialDigits(int low, int high) {
    List<Integer> resultList = new ArrayList<>();
    for (int value : seq.sequenceList) {
      if (value >= low && value <= high) resultList.add(value);
    }
    return resultList;
  }
}