Solution For Sequential Digits
Problem Statement:
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:
Input: low = 100, high = 300
Output: [123,234]
Solution:
The approach for this problem can be to check all numbers between the range (low, high) and check if they have sequential digits. If a number has sequential digits, add it to the result list.
To check if a number has sequential digits, we can extract all its digits and check if the difference between any two adjacent digits is equal to 1. If all the differences are 1, then the number has sequential digits.
We need to consider all possible length of sequential digits from 2 to 9. For each length, we can generate all possible numbers of that length which have sequential digits and add them to the result list if they lie in the given range.
Code:
“`
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
digits = “123456789” # All possible digits
res = []
for length in range(2, 10): # Check for all possible length of sequential digits
for i in range(0, 10 - length): # Generate all possible starting positions
num = int(digits[i:i+length]) # Extract the number from digits
if low <= num <= high:
res.append(num) # Add to the result list if it lies in range
return res
“`
Time Complexity:
As we are checking all possible numbers in the given range, the time complexity of the above solution will be O(N), where N is the number of integers between low and high.
Space Complexity:
The space complexity of the above solution will be O(N), where N is the number of integers between low and high that have sequential digits.
Step by Step Implementation For Sequential Digits
class Solution {
public List sequentialDigits(int low, int high) {
List result = new ArrayList<>();
// TODO: Write your code here
return result;
}
} class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
# Initialize a list to store the results
results = []
# Loop through all numbers starting from low to high
for num in range(low, high+1):
# Convert the number to a list of digits
digits = [int(x) for x in str(num)]
# Initialize a flag to check if the number is sequential
is_sequential = True
# Loop through the digits and check if they are sequential
for i in range(len(digits)-1):
if digits[i]+1 != digits[i+1]:
is_sequential = False
break
# If the number is sequential, add it to the results
if is_sequential:
results.append(num)
# Return the results
return resultsvar sequentialDigits = function(low, high) {
// create a variable to store all possible sequential digits
let possibleSequentialDigits = [];
// create a variable to store the current number we are checking
// set this variable equal to low
let currentNumber = low;
// create a while loop that will continue until currentNumber is greater than high
while (currentNumber < high) {
// create a variable to store the current number as a string
let currentNumberString = currentNumber.toString();
// create a variable to store the length of the current number string
let currentNumberStringLength = currentNumberString.length;
// create a variable to store the value of the first digit in the current number string
let firstDigit = parseInt(currentNumberString[0]);
// create a variable to store the value of the last digit in the current number string
let lastDigit = parseInt(currentNumberString[currentNumberStringLength - 1]);
// create a variable to store the value of the next sequential digit
// set this equal to lastDigit + 1
let nextDigit = lastDigit + 1;
// create a variable to store the value of the next sequential number
// set this equal to firstDigit + nextDigit
let nextNumber = firstDigit + nextDigit;
// create a variable to store the value of the next sequential number as a string
// set this equal to nextNumber.toString()
let nextNumberString = nextNumber.toString();
// create a variable to store the length of the next sequential number string
// set this equal to nextNumberString.length
let nextNumberStringLength = nextNumberString.length;
// create an if statement that checks if the length of the next sequential number string is equal to the length of the current number string
if (nextNumberStringLength === currentNumberStringLength) {
// create a variable to store the value of the next sequential digit
// set this equal to the last digit in the next sequential number string
nextDigit = parseInt(nextNumberString[nextNumberStringLength - 1]);
// create a variable to store the value of the next sequential number
// set this equal to firstDigit + nextDigit
nextNumber = firstDigit + nextDigit;
// create a variable to store the value of the next sequential number as a string
// set this equal to nextNumber.toString()
nextNumberString = nextNumber.toString();
// create a variable to store the length of the next sequential number string
// set this equal to nextNumberString.length
nextNumberStringLength = nextNumberString.length;
}
// create an if statement that checks if the length of the next sequential number string is equal to the length of the current number string + 1
if (nextNumberStringLength === currentNumberStringLength + 1) {
// create a variable to store the value of the first digit in the next sequential number string
// set this equal to firstDigit + 1
let nextFirstDigit = firstDigit + 1;
// create a variable to store the value of the next sequential number
// set this equal to nextFirstDigit + nextDigit
nextNumber = nextFirstDigit + nextDigit;
// create a variable to store the value of the next sequential number as a string
// set this equal to nextNumber.toString()
nextNumberString = nextNumber.toString();
// create a variable to store the length of the next sequential number string
// set this equal to nextNumberString.length
nextNumberStringLength = nextNumberString.length;
}
// create an if statement that checks if the next sequential number is less than or equal to high
if (nextNumber <= high) {
// push the next sequential number into the possibleSequentialDigits array
possibleSequentialDigits.push(nextNumber);
// set currentNumber equal to the next sequential number
currentNumber = nextNumber;
}
// if the next sequential number is greater than high, set currentNumber equal to high + 1
else {
currentNumber = high + 1;
}
}
// return the possibleSequentialDigits array
return possibleSequentialDigits;
};class Solution {
public:
vector sequentialDigits(int low, int high) {
// vector to store output
vector output;
// base case
if(low == 0) {
output.push_back(1);
}
// loop through all possible digits
for(int digit = 1; digit <= 9; digit++) {
// start building number with current digit
int num = digit;
int next = digit + 1;
// keep adding digits until number is out of range
while(num <= high && next <= 9) {
// if number is in range, add to output
if(num >= low) {
output.push_back(num);
}
// increment number and next digit
num = num * 10 + next;
next++;
}
}
return output;
}
}; using System;
public class Solution {
// Function to generate sequential digits
static void generateSequentialDigits(int low, int high)
{
// To store the result
List < int > res = new List < int > ();
// Loop to generate sequential digits
for (int i = 1; i <= 9; i++)
{
int num = i;
// Loop to append next digit
while (num <= high && num % 10 != 9)
{
// If number lies in given range,
// then append it to the result
if (num >= low)
res.Add(num);
// Append next digit
num = num * 10 + (num % 10) + 1;
}
}
// Print the result
foreach(int i in res)
Console.Write(i + " ");
}
// Driver code
public static void Main()
{
int low = 100, high = 300;
generateSequentialDigits(low, high);
}
}