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
Companies:
Splunk
Related Topics:
Enumeration
get function: Given length and first digit, generate the number.
Get the length of low, and start creating numbers from this length. Keep only the numbers in range.
// OJ: https://leetcode.com/problems/sequential-digits/
// Author: github.com/lzl124631x
// 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;
}
};// OJ: https://leetcode.com/problems/sequential-digits/
// Author: github.com/lzl124631x
// Time: O(1) since there are limited number of valid integers
// Space: O(1)
class Solution {
int next(int n, int increment = 1) {
int len = log10(n), first = n / pow(10, len) + increment;
if (first > 9 - len) {
first = 1;
++len;
}
int ans = first;
while (len--) ans = 10 * ans + ++first;
return ans;
}
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
int n = next(low, 0);
while (n < low) n = next(low);
for (; n <= high; n = next(n)) {
ans.push_back(n);
}
return ans;
}
};