Name:Unknown
Clan:Unknown
Member Since:Aug 2021
Last Seen:Sep 2024
Profiles:
Following:0
Followers:0
Allies:0
Algorithms
Due to the fact that the array is sorted, each subsequent element is greater than the previous one by 1 and only one element is missing, we can use binary search, since before the missing int, all numbers in the sequence are equal to index + sequence[0], and everything after the missing int is greater than the expression index + sequence[0] by 1.
Thus, the array is divided into two halves by the point at which "the right element is greater than its real value, and the left element corresponds to its real value."
Due to binary search, the time complexity of the algorithm is O(log(n)), and due to the fact that the "correct" value can be calculated from the formula, there is no need to construct a range as in the previous solutions.
from typing import Sequence def missing_integer(seq: Sequence[int]) -> int | None: lo, hi = 0, len(seq) while lo < hi: mid = (lo + hi) // 2 real = seq[mid] must_be = seq[0] + mid if real > must_be: if must_be - 1 == seq[mid - 1]: return must_be hi = mid if real == must_be: lo = mid + 1from typing import Sequence, Optional- from typing import Sequence
def missing_integer(sequence: Sequence[int]) -> Optional[int]:for x, y in zip(sequence, range(sequence[0], sequence[-1])):if x != y:return y- def missing_integer(seq: Sequence[int]) -> int | None:
- lo, hi = 0, len(seq)
- while lo < hi:
- mid = (lo + hi) // 2
- real = seq[mid]
- must_be = seq[0] + mid
- if real > must_be:
- if must_be - 1 == seq[mid - 1]:
- return must_be
- hi = mid
- if real == must_be:
- lo = mid + 1
import codewars_test as test from solution import missing_integer @test.describe("Find the missing integer in a sorted sequence of natural numbers.") def test_group(): @test.it("Comparing to expected return values.") def test_case(): test.assert_equals(missing_integer([1, 2, 3, 4, 5, 7, 8, 9]), 6) test.assert_equals(missing_integer([1, 2, 4, 5, 6, 7, 8, 9]), 3) test.assert_equals(missing_integer([1, 2, 3, 4, 5, 6, 7, 9]), 8) test.assert_equals(missing_integer([-2, 0, 1, 2, 3, 4, 5, 6]), -1) test.assert_equals(missing_integer([1, 2, 3, 4, 5, 6, 7, 8, 9]), None)- import codewars_test as test
- from solution import missing_integer
- @test.describe("Find the missing integer in a sorted sequence of natural numbers.")
- def test_group():
- @test.it("Comparing to expected return values.")
- def test_case():
- test.assert_equals(missing_integer([1, 2, 3, 4, 5, 7, 8, 9]), 6)
- test.assert_equals(missing_integer([1, 2, 4, 5, 6, 7, 8, 9]), 3)
- test.assert_equals(missing_integer([1, 2, 3, 4, 5, 6, 7, 9]), 8)
- test.assert_equals(missing_integer([-2, 0, 1, 2, 3, 4, 5, 6]), -1)
- test.assert_equals(missing_integer([1, 2, 3, 4, 5, 6, 7, 8, 9]), None)