Feature #9: Kth Missing Gene
Explore how to identify the kth missing gene in a sorted DNA sequence by applying binary search techniques. Understand the algorithm that calculates the number of missing genes before each gene and how this insight helps locate the missing gene efficiently with logarithmic time complexity and constant space.
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 missing gene in a sorted order. The given DNA sequence will be sorted in strictly increasing order.
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 arr in order to use the binary search algorithm. To find the number of missing genes, we will compare our input array, arr, with an array that has no missing genes.
Suppose that the input array, arr, is [2, 3, 4, 7, 11]. We will compare it to an array with no missing genes, that is, [1,2,3,4,5]. The number of missing genes ...