Search⌘ K
Home
Courses
Decode the Coding Interview in Java: Real-World Examples

Feature #9: Kth Missing Gene

Explore how to identify the kth missing gene within a sorted DNA sequence using binary search. This lesson helps you understand how to calculate missing genes before a given point and apply an efficient algorithm with O(log n) time complexity. Learn to map this approach to related coding interview problems in computational biology.

We'll cover the following...

Description

A planet has n genes, numbered 1 to n. Every species on the planet has a subset of these genes in its DNA sequence. For a given species’ DNA, A, we want to find the kthk^{th} missing gene in a sorted order. The given DNA sequence will be sorted in strictly increasing order.

Constraints

  • 1 <= A[i] <= 1000
  • 1<= k <= 1000
  • A[i] <= A[j] for 1 <= i < j <= A.length

The following examples may clarify this problem:

Solution

Our input is sorted in an ascending order. We can use this fact and try to solve this problem using binary search. However, we need to find the number of missing genes that come before a given gene in the DNA A in order to use the binary search algorithm. To find the number of missing genes, we will compare our input array, A, with an array that has no missing genes.

Suppose that the input array, ...