How to implement an algorithm to detect if a number has 2 consecutive digits?

user_8243324 0
Viewed 365

I want to create a function that returns true if a number has consecutive digits or not,

example:

  • if the input is 11, it will return true
  • if the input is 21 it will return false
  • if the input is 323 it will return false because even though we have 3 repeated, they are not consecutive

My solution right now is to transform the number into an array and loop through the number one by one, if the next number is equal to the current number then we just return true. But this has a complexity time of O(n) and I was wondering if anyone can come with a better solution.

Thank you

arrays algorithm javascript
4 Answers

There is an arguably better solution where you don't need to convert the number into a string or array of numbers/character. It works as follows:

  1. Initialize a variable curr to -1.
  2. Run a loop while num > 0 and do the following:
  • next_curr = num % 10
  • if next_curr == curr: return true
  • curr = next_curr
  • num = num / 10 (integer division)
  1. If the loop completes, return false.

This is a one pass O(log n) time complexity algorithm where n is the input number. The space complexity is O(1)

Note that while your algorithm was also O(log n) time complexity, it did 2 passes, and had a space complexity of O(log n) too.

I haven't written JS for some time now, but here's a possible implementation of the above algorithm in JS:

function sameAdjacentDigits(num) {
    // to deal with negative numbers and
    // avoid potential problems when using Math.floor later
    num = Math.abs(num)
    let curr = -1
    while (num > 0) {
        const nextCurr = num % 10
        if (nextCurr == curr) return true
        curr = nextCurr
        num = Math.floor(num / 10)
    }
    return false
}
user_77556650
user_13561070

Easiest way to execute this is by using regex. Not sure what would be effectiveness of algorithm, but solution could be

/(\d)\1/

user_12300870

Inspired from @Tschallacka's answer:

let numbers = [11,21,323];

let result = numbers.map(n=>{
  let test = n.toString().match(/(00|11|22|33|44|55|66|77|88|99)/);
  return test != null;
})

console.log(result);

user_21595280
Related