2

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

Improve this question
6
  • 1
    Can you show what you have attempted? Hard to imagine something better than O(n) for this purpose. Commented Jan 15, 2022 at 19:19
  • 3
    You obviously need to examine all the digits to check for identity, so you're unlikely to be able to go below o(n) with n = number of digits. Commented Jan 15, 2022 at 19:33
  • 2
    Your O(n) algorithm is the best time complexity you can get for this problem. Solutions involving regular expressions are just delegating the loop to the regex engine. Commented Jan 15, 2022 at 19:36
  • @BilltheLizard: for super long numbers like 2345674396539588934682364823553 and more... I think the regex would do only 10 iterations (see my answer). So it should be faster. Commented Jan 15, 2022 at 19:44
  • 1
    @louys wrong. Have you checked the implementation of the RegEx engine to back your claim? Or run any performance comparison? If not, stop guessing. Commented Jan 15, 2022 at 20:13

4 Answers 4

Reset to default
3

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
}
Improve this answer
Sign up to request clarification or add additional context in comments.

16 Comments

@skara9 The OP converts a number to an array, so the initial input is a number, not a string.
@skara9 I'm afraid your are going too far :-|
If you're looping over the digits of the input, then n should be the length of the input, not its value. This algorithm is also O(n).
@BilltheLizard Yes I was wondering about that, "n is the input number" sounds weird to me.
I think I got it. O(log n) is right since log n is the number of digits, then I suppose the confusion comes from the name of the variable n since O(log n) is a naming convention in computer science. Writing "This is a one pass O(n) time complexity algorithm where n = log(x) is the number of digits of the input number x." is probably better. Am I right?
|
1

Use some regex, and then check what was found via the matcher

numbers_match = /(00|11|22|33|44|55|66|77|88|99)/;
numbers_match.match("11")

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/match

Improve this answer

1 Comment

Thank you but about the time complexity, don't you think it's still O(n)?
1

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

/(\d)\1/

Improve this answer

Comments

0

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);

Improve this answer

3 Comments

Thanks for your help, but I am not sure about the time complexity of regex, I think it still has to loop to all of the strings to find the match right?
I'm am unsure how regex is performing the loop internally... But I assume it should loop only 10 times (for the ten possibilities). So on super long numbers, it should be faster than iterating all digits... Again, I am unsure about it.
I made an attempt to measure the execution time on CodePen and... It looks like less than a millisecond even for a BigInt.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.