Given an unsorted sequence a[], the task is to find the K-th missing contiguous element in the increasing sequence of the array elements i.e. consider the array in sorted order and find the kth missing number. If no k-th missing element is there output -1.
Note: Only elements exists in the range of minimum and maximum element to be considered.
Examples:
Input: arr[] = {2, 4, 10, 7}, k = 5
Output: 9
Missing elements in the given array: 3, 5, 6, 8, 9
5th missing is 9.
Input: arr[] = {1, 3, 4}, k = 5
Output: -1
Method-1: Sort the array and use the approach used in the k-th missing element in a sorted array.
Method-2:
- Insert all the elements in an unordered_set.
- Find the minimum and maximum element of the array.
- Traverse the elements from minimum to maximum.
- Check if current element is present in the set or not.
- If not then check if this is kth missing by counting the missing elements.
- Return the current element if this is current missing.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the sum// of minimum of all subarraysint findKth(int arr[], int n, int k){ unordered_set<int> missing; int count = 0; // Insert all the elements in a set for (int i = 0; i < n; i++) missing.insert(arr[i]); // Find the maximum and minimum element int maxm = *max_element(arr, arr + n); int minm = *min_element(arr, arr + n); // Traverse from the minimum to maximum element for (int i = minm + 1; i < maxm; i++) { // Check if "i" is missing if (missing.find(i) == missing.end()) count++; // Check if it is kth missing if (count == k) return i; } // If no kth element is missing return -1;}// Driver codeint main(){ int arr[] = { 2, 10, 9, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 5; cout << findKth(arr, n, k); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{ // Function to find the sum // of minimum of all subarrays static int findKth(int arr[], int n, int k) { HashSet<Integer> missing = new HashSet<>(); int count = 0; // Insert all the elements in a set for (int i = 0; i < n; i++) { missing.add(arr[i]); } // Find the maximum and minimum element int maxm = Arrays.stream(arr).max().getAsInt(); int minm = Arrays.stream(arr).min().getAsInt(); // Traverse from the minimum to maximum element for (int i = minm+1; i < maxm; i++) { // Check if "i" is missing if (!missing.contains(i)) { count++; } // Check if it is kth missing if (count == k) { return i; } } // If no kth element is missing return -1; } // Driver code public static void main(String[] args) { int arr[] = {2, 10, 9, 4}; int n = arr.length; int k = 5; System.out.println(findKth(arr, n, k)); }}/* This code contributed by PrinciRaj1992 */ |
Python
# Python3 implementation of the above approach# Function to find the sum# of minimum of all subarraysdef findKth( arr, n, k): missing = dict() count = 0 # Insert all the elements in a set for i in range(n): missing[arr[i]] = 1 # Find the maximum and minimum element maxm = max(arr) minm = min(arr) # Traverse from the minimum to maximum element for i in range(minm + 1, maxm): # Check if "i" is missing if (i not in missing.keys()): count += 1 # Check if it is kth missing if (count == k): return i # If no kth element is missing return -1# Driver codearr = [2, 10, 9, 4 ]n = len(arr)k = 5print(findKth(arr, n, k))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the above approach using System;using System.Linq;using System.Collections.Generic;class GFG { // Function to find the sum // of minimum of all subarrays static int findKth(int []arr, int n, int k) { HashSet<int> missing = new HashSet<int>(); int count = 0; // Insert all the elements in a set for (int i = 0; i < n; i++) { missing.Add(arr[i]); } // Find the maximum and minimum element int maxm = arr.Max(); int minm = arr.Min(); // Traverse from the minimum to maximum element for (int i = minm + 1; i < maxm; i++) { // Check if "i" is missing if (!missing.Contains(i)) { count++; } // Check if it is kth missing if (count == k) { return i; } } // If no kth element is missing return -1; } // Driver code public static void Main(String[] args) { int []arr = {2, 10, 9, 4}; int n = arr.Length; int k = 5; Console.WriteLine(findKth(arr, n, k)); } } // This code has been contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the above approach // Function to find the sum // of minimum of all subarrays function findKth($arr, $n, $k){ $missing = array(); $count = 0; // Insert all the elements in a set for ($i = 0; $i < $n; $i++) array_push($missing, $arr[$i]); $missing = array_unique($missing); // Find the maximum and minimum element $maxm = max($arr); $minm = min($arr); // Traverse from the minimum to // maximum element for ($i = $minm + 1; $i < $maxm; $i++) { // Check if "i" is missing if (!in_array($i, $missing, false)) $count += 1; // Check if it is kth missing if ($count == $k) return $i; } // If no kth element is missing return -1;}// Driver code $arr = array(2, 10, 9, 4); $n = sizeof($arr); $k = 5;echo findKth($arr, $n, $k);// This code is contributed by Ryuga?> |
Javascript
<script>// javascript implementation of the above approach// Function to find the sum// of minimum of all subarraysfunction findKth(arr, n, k){ var missing = new Set(); var count = 0; // Insert all the elements in a set for (var i = 0; i < n; i++) missing.add(arr[i]); // Find the maximum and minimum element var maxm = arr.reduce((a,b)=>Math.max(a,b)); var minm = arr.reduce((a,b)=>Math.min(a,b)); // Traverse from the minimum to maximum element for (var i = minm + 1; i < maxm; i++) { // Check if "i" is missing if (!missing.has(i)) count++; // Check if it is kth missing if (count == k) return i; } // If no kth element is missing return -1;}// Driver codevar arr = [ 2, 10, 9, 4 ];var n = arr.length;var k = 5;document.write( findKth(arr, n, k));// This code is contributed by noob2000.</script> |
Output:
8
Time complexity: O(n) where n is size of input array
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] There you can find 86248 additional Info on that Topic: geeksforgeeks.org/k-th-missing-element-in-an-unsorted-array/ […]
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/k-th-missing-element-in-an-unsorted-array/ […]