Given an array of size N and two integers M and K., All the integers in the array are in the range [1, M]. Find if any possible subsequence of size K is missing in the array, such that all the integers of that subsequence are also in the range [1, M].
Examples:
Input: arr[] = {2, 3, 3, 1, 2, 3, 2}, M = 3, K = 3
Output: YES
Explanation: The sequence {1, 3, 2} of size 3 is missing in the array
and there are many other subsequences also which are missing in the arrayInput: arr[] = {4, 3, 1, 3, 2, 4, 1, 1, 2, 3}, M = 4, K = 2
Output: NO
Explanation: No subsequence of size 2 is missing from the array
Find missing subsequence of size K using hashing:
Find continuous blocks of integers in the array, which contains all the numbers in the range [1, M]. If one such block is found then every subsequence of size 1 is present in the array, as every number appears once in this block.
Similarly if two such blocks are found in the array, then every subsequence of size 2 is present in the array and so on. So if count of such blocks is less than K, then the answer is “YES”, else “NO”
Follow the given steps to solve the problem:
- Declare a map to store the count of every integer and two variables count and freq, to store the number of blocks found and number of distinct integers found in this current block respectively
- Iterate through the array
- Increase the count of every element on the map
- If the element is seen for the first time, then increase the freq by one
- If freq is equal to M( which means that one block is found), then increase the count variable by one and clear the map, and set the freq variable back to zero, so that the next block can be found
- If the count of such blocks is less than K, then the answer is “YES”, else “NO”
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find if a subsequence// of size K is missing or notint findBlocks(vector<int>& arr, int N, int M){ int count = 0, freq = 0; unordered_map<int, int> mp; // Traverse the array to find the // number of blocks for (int i = 0; i < N; i++) { mp[arr[i]]++; // If an element is seen for the // first time then increase freq if (mp[arr[i]] == 1) freq++; // If freq is equal to M then // it means a block is found // so increase the value of count // by one if (freq == M) { count++; freq = 0; mp.clear(); } } return count;}// Driver codeint main(){ vector<int> arr = { 2, 3, 3, 1, 2, 3, 2 }; int N = 7, M = 3, K = 3; // Function call int count = findBlocks(arr, N, M); if (count < K) cout << "YES" << endl; else cout << "NO" << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG{ // Function to find if a subsequence // of size K is missing or not static int findBlocks(List<Integer> arr, int N, int M) { int count = 0, freq = 0; HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Traverse the array to find the // number of blocks for (int i = 0; i < N; i++) { if(mp.containsKey(arr.get(i))){ mp.put(arr.get(i), mp.get(arr.get(i))+1); }else{ mp.put(arr.get(i), 1); } // If an element is seen for the // first time then increase freq if (mp.get(arr.get(i)) == 1) freq++; // If freq is equal to M then // it means a block is found // so increase the value of count // by one if (freq == M) { count++; freq = 0; mp.clear(); } } return count; } // Driver code public static void main(String[] args) { Integer [] a = new Integer[]{ 2, 3, 3, 1, 2, 3, 2 }; List<Integer> arr = Arrays.asList(a); int N = 7, M = 3, K = 3; // Function call int count = findBlocks(arr, N, M); if (count < K) System.out.print("YES" +"\n"); else System.out.print("NO" +"\n"); }}// This code is contributed by shikhasingrajput |
Python3
# Python3 code to implement the approach# Function to find if a subsequence# of size K is missing or notdef findBlocks(arr, N, M) : count = 0; freq = 0; mp = {} ; # Traverse the array to find the # number of blocks for i in range(N) : if arr[i] in mp : mp[arr[i]] += 1 else : mp[arr[i]] = 1 # If an element is seen for the # first time then increase freq if (mp[arr[i]] == 1) : freq += 1; # If freq is equal to M then # it means a block is found # so increase the value of count # by one if (freq == M) : count += 1; freq = 0; mp = {}; return count;# Driver codeif __name__ == "__main__" : arr = [ 2, 3, 3, 1, 2, 3, 2 ]; N = 7; M = 3; K = 3; # Function call count = findBlocks(arr, N, M); if (count < K) : print("YES"); else : print("NO"); # This code is contributed by AnkThon |
C#
using System;using System.Collections.Generic;public class GFG { // Function to find if a subsequence // of size K is missing or not static int findBlocks(int[] arr, int N, int M) { int count = 0, freq = 0; Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array to find the // number of blocks for (int i = 0; i < N; i++) { if (mp.ContainsKey(arr[i])) { mp[arr[i]]++; } else { mp.Add(arr[i], 1); } // If an element is seen for the // first time then increase freq if (mp[arr[i]] == 1) freq++; // If freq is equal to M then // it means a block is found // so increase the value of count // by one if (freq == M) { count++; freq = 0; mp.Clear(); } } return count; } // Driver code static public void Main() { int[] arr = { 2, 3, 3, 1, 2, 3, 2 }; int N = 7, M = 3, K = 3; // Function call int count = findBlocks(arr, N, M); if (count < K) Console.Write("YES" + "\n"); else Console.Write("NO" + "\n"); }}// This code is contributed by Rohit Pradhan |
Javascript
<script>// Javascript code to implement the approach// Function to find if a subsequence// of size K is missing or notfunction findBlocks( arr, N, M){ let count = 0, freq = 0; let mp = new Map(); // Traverse the array to find the // number of blocks for (let i = 0; i < N; i++) { mp[arr[i]]++; // If an element is seen for the // first time then increase freq if (mp[arr[i]] == 1) freq++; // If freq is equal to M then // it means a block is found // so increase the value of count // by one if (freq == M) { count++; freq = 0; mp.clear(); } } return count;}// Driver code let arr = [ 2, 3, 3, 1, 2, 3, 2 ]; let N = 7, M = 3, K = 3; // Function call let count = findBlocks(arr, N, M); if (count < K) document.write("YES"); else document.write("NO"); // This code is contributed by satwik4409. </script> |
Output
YES
Time Complexity: O(N)
Auxiliary Space: O(N)
