k-th missing element in increasing sequence which is not present in a given sequence

Difficulty Level Easy
Frequently asked in Citadel Expedia Fab Factset IBM SAP Labs
Array Hash SearchingViews 1849

The problem “k-th missing element in increasing sequence which is not present in a given sequence” states that you are given two arrays. One of them is arranged in ascending order and another normal unsorted array with number k. Find the kth missing element which is not present in normal sequence but is present in increasing order sequence array.

Example

k-th missing element in increasing sequence which is not present in a given sequence

[0, 2, 4, 6, 8, 10, 12, 14]
[4, 10, 6, 12, 2 ]
k=2
8

Explanation

The numbers in the increasing sequence which are not present in the given array are 0,8,14.

The kth missing number i.e., 2nd number is 8

Algorithm to find k-th missing element in increasing sequence which is not present in a given sequence

  1. Declare a HashSet.
  2. Put all the elements of the second array into HashSet.
  3. Set missingCount to 0.
  4. While traversing the increasing sequential array, check:
    1. If a set does not contain any of the sequential array element
      1. Increase the missingCount value by 1.
      2. Check if missingCount value is equal to k.
        • If true, return that array[i].
  5. Out of the loop, return -1.

Explanation

You are given two arrays and a number k. One of the two arrays is an increasing sequence and the other one is a normal unsorted sequence. The problem statement says that you have to find the kth missing element in the sorted sequence array which is not present in the unsorted array.

We are going to use a Set for this. We are going to traverse the second array b[] and insert all of its value into the set. This is because we can check it later and compare the set with the first array a[]. While traversing the array a [], if the set does not contain that particular value of array a[i]. We increase the value of missingCount by 1 and simultaneously check if missingCount becomes equal to the given number k. If it does, we can return that element of the first array.

Let us consider an example and understand this.

Example

array a[] = [0, 2, 4, 6, 8, 10, 12, 14]

b[] = [4, 10, 6, 12, 2 ]

k=2

As per algorithm, we need to put array b[] elements into set. We will do this by traversing the array b[].

Our set will become { 4, 10, 6, 12, 2}

We need to traverse the array a[] elements and check if set does not contain arr [i] element,

i=0, arr[i] = 0

Set does not contain it so it will increase missingCount=missingCount+1

missingCount =1, check if missingCount==k, it is false.

i=1, arr[i] = 2

set contains that value ‘2’, so it do nothing.

i=2, arr[i] = 4

set contains that value ‘4’, so it do nothing.

i=3, arr[i] = 6

set contains that value ‘6’, so it do nothing.

i=4, arr[i]=8

Set does not contain 8, so it will increase missingCount=missingCount+1

missingCount =2, check if missingCount==k, it is true so it will return arr[i] that is ‘8’,

The output will become 8.

Code

C++ code to find k-th missing element in increasing sequence which is not present in a given sequence

#include <unordered_set>
#include<iostream>

using namespace std;
int find(int A[], int B[], int k, int l1, int l2)
{
  unordered_set<int> myset;
  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  int missingCount = 0;
  for (int i = 0; i < l1; i++) {
    if (myset.find(A[i]) == myset.end())
      missingCount++;
    if (missingCount == k)
      return A[i];
  }

  return -1;
}
int main()
{
    int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
    int b[] = { 4, 10, 6, 12, 2 };

  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);

  int k = 2;
  cout << find(a, b, k, l1, l2);
  return 0;
}

8

Java code to find k-th missing element in increasing sequence which is not present in a given sequence

import java.util.LinkedHashSet;

class kthMissingElement
{
    public static int getMissingElement(int A[], int B[], int k, int l1, int l2)
    {
        LinkedHashSet<Integer> hashset = new LinkedHashSet<>();
        for (int i = 0; i < l2; i++)
            hashset.add(B[i]);

        int missingCount = 0;
        for (int i = 0; i < l1; i++)
        {
            if(!hashset.contains(A[i]) )
                missingCount++;
            if (missingCount == k)
                return A[i];
        }

        return -1;
    }
    public static void main(String[] args)
    {
        int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
        int b[] = { 4, 10, 6, 12, 2 };
        int l1 = a.length;
        int l2 = b.length;

        int k = 2;
        System.out.println(getMissingElement(a, b, k, l1, l2));
    }
}

8

Complexity Analysis

Time Complexity

O(n1 + n2) where “n1” and “n2” are length of array1 and array2. Since we have traversed all of the elements from both of the arrays. The time complexity is linear.

Space Complexity

O(n2) where “n2” is the length of array2. Because we have stored only the elements of the second array into the HashSet, the space required is also linear.

Translate »