Formatted question description: https://leetcode.ca/all/1291.html

1291. Sequential Digits (Medium)

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

 

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

Related Topics:
Backtracking

Solution 1.

// OJ: https://leetcode.com/problems/sequential-digits/
// Time: O(1) since there are limited number of valid integers
// Space: O(1)
class Solution {
    long get(int start, int len) {
        long ans = 0;
        while (len-- > 0) {
            ans = ans * 10 + start;
            ++start;
        }
        return ans;
    }
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;
        int len = 0, tmp = len;
        while (tmp) {
            tmp /= 10;
            ++len;
        }
        while (len <= 9) {
            for (int i = 1; i <= 9 - len + 1; ++i) {
                long long n = get(i, len);
                if (n < low) continue;
                if (n > high) return ans;
                ans.push_back(n);
            }
            ++len;
        }
        return ans;
    }
};

Java

  • class Solution {
        public List<Integer> sequentialDigits(int low, int high) {
            if (high == 1000000000)
                high--;
            List<Integer> list = new ArrayList<Integer>();
            int lengthLow = String.valueOf(low).length(), lengthHigh = String.valueOf(high).length();
            List<Integer> listLow = sequentialDigitsWithLength(lengthLow);
            for (int num : listLow) {
                if (num > high)
                    break;
                if (num >= low)
                    list.add(num);
            }
            for (int i = lengthLow + 1; i < lengthHigh; i++) {
                List<Integer> listWithLength = sequentialDigitsWithLength(i);
                for (int num : listWithLength)
                    list.add(num);
            }
            List<Integer> listHigh = sequentialDigitsWithLength(lengthHigh);
            if (lengthLow < lengthHigh) {
                for (int num : listHigh) {
                    if (num <= high)
                        list.add(num);
                    else
                        break;
                }
            }
            return list;
        }
    
        public List<Integer> sequentialDigitsWithLength(int length) {
            List<Integer> list = new ArrayList<Integer>();
            int begin = 1, end = 9 - length + 1;
            int num = 0;
            int inc = 0;
            int digit = 1;
            while (digit <= length) {
                num *= 10;
                num += digit;
                digit++;
                inc *= 10;
                inc++;
            }
            for (int i = begin; i <= end; i++) {
                list.add(num);
                num += inc;
            }
            return list;
        }
    }
    
  • // OJ: https://leetcode.com/problems/sequential-digits/
    // Time: O(1) since there are limited number of valid integers
    // Space: O(1)
    class Solution {
        long get(int start, int len) {
            long ans = 0;
            while (len-- > 0) {
                ans = ans * 10 + start;
                ++start;
            }
            return ans;
        }
    public:
        vector<int> sequentialDigits(int low, int high) {
            vector<int> ans;
            int len = 0;
            for (int tmp = low; tmp; tmp /= 10) ++len;
            while (len <= 9) {
                for (int i = 1; i <= 9 - len + 1; ++i) {
                    long long n = get(i, len);
                    if (n < low) continue;
                    if (n > high) return ans;
                    ans.push_back(n);
                }
                ++len;
            }
            return ans;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions