Given an array arr[] consisting of N integers and two positive integers M and K, the task is to check if there exists any subarray of length M that repeats consecutively at least K times. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {2, 1, 2, 1, 1, 1, 3}, M = 2, K = 2
Output: Yes
Explanation: The subarray {2, 1} of length 2 repeats at least K(= 2) times consecutively.Input: arr[] = {7, 1, 3, 1, 1, 1, 1, 3}, M = 1, K = 3
Output: Yes
Naive Approach: The simplest approach is to generate all possible subarrays of length M and check for each subarray, whether on concatenating it exactly K times is present as a subarray in the given array or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to check if there exists // any subarray of length M repeating // at least K times consecutively bool check(int arr[], int M, int K, int ind) { // Iterate from i equal 0 to M for (int i = 0; i < M; i++) { // Iterate from j equals 1 to K for (int j = 1; j < K; j++) { // If elements at pos + i and // pos + i + j * M are not equal if (arr[ind + i] != arr[ind + i + j * M]) { return false; } } } return true; } // Function to check if a subarray repeats // at least K times consecutively or not bool SubarrayRepeatsKorMore( int arr[], int N, int M, int K) { // Iterate from ind equal 0 to M for (int ind = 0; ind <= N - M * K; ind++) { // Check if subarray arr[i, i + M] // repeats atleast K times or not if (check(arr, M, K, ind)) { return true; } } // Otherwise, return false return false; } // Driver Code int main() { int arr[] = { 2, 1, 2, 1, 1, 1, 3 }; int M = 2, K = 2; int N = sizeof(arr) / sizeof(arr[0]); if (SubarrayRepeatsKorMore( arr, N, M, K)) { cout << "Yes"; } else { cout << "No"; } return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to check if there exists // any subarray of length M repeating // at least K times consecutively static boolean check(int arr[], int M, int K, int ind) { // Iterate from i equal 0 to M for(int i = 0; i < M; i++) { // Iterate from j equals 1 to K for(int j = 1; j < K; j++) { // If elements at pos + i and // pos + i + j * M are not equal if (arr[ind + i] != arr[ind + i + j * M]) { return false; } } } return true; } // Function to check if a subarray repeats // at least K times consecutively or not static boolean SubarrayRepeatsKorMore(int arr[], int N, int M, int K) { // Iterate from ind equal 0 to M for(int ind = 0; ind <= N - M * K; ind++) { // Check if subarray arr[i, i + M] // repeats atleast K times or not if (check(arr, M, K, ind)) { return true; } } // Otherwise, return false return false; } // Driver Code public static void main(String[] args) { int arr[] = { 2, 1, 2, 1, 1, 1, 3 }; int M = 2, K = 2; int N = arr.length; if (SubarrayRepeatsKorMore(arr, N, M, K)) { System.out.println("Yes"); } else { System.out.println("No"); } } } // This code is contributed by Kingash |
Python3
# Python3 program for the above approach # Function to check if there exists # any subarray of length M repeating # at least K times consecutively def check(arr, M, K, ind): # Iterate from i equal 0 to M for i in range(M): # Iterate from j equals 1 to K for j in range(1, K, 1): # If elements at pos + i and # pos + i + j * M are not equal if (arr[ind + i] != arr[ind + i + j * M]): return False return True # Function to check if a subarray repeats # at least K times consecutively or not def SubarrayRepeatsKorMore(arr, N, M, K): # Iterate from ind equal 0 to M for ind in range(N - M * K + 1): # Check if subarray arr[i, i + M] # repeats atleast K times or not if (check(arr, M, K, ind)): return True # Otherwise, return false return False # Driver Code if __name__ == '__main__': arr = [2, 1, 2, 1, 1, 1, 3] M = 2 K = 2 N = len(arr) if (SubarrayRepeatsKorMore(arr, N, M, K)): print("Yes") else: print("No") # This code is contributed by bgangwar59 |
C#
// C# program for the above approach using System; class GFG{ // Function to check if there exists // any subarray of length M repeating // at least K times consecutively static bool check(int[] arr, int M, int K, int ind) { // Iterate from i equal 0 to M for(int i = 0; i < M; i++) { // Iterate from j equals 1 to K for(int j = 1; j < K; j++) { // If elements at pos + i and // pos + i + j * M are not equal if (arr[ind + i] != arr[ind + i + j * M]) { return false; } } } return true; } // Function to check if a subarray repeats // at least K times consecutively or not static bool SubarrayRepeatsKorMore(int[] arr, int N, int M, int K) { // Iterate from ind equal 0 to M for(int ind = 0; ind <= N - M * K; ind++) { // Check if subarray arr[i, i + M] // repeats atleast K times or not if (check(arr, M, K, ind)) { return true; } } // Otherwise, return false return false; } // Driver code static void Main() { int[] arr = { 2, 1, 2, 1, 1, 1, 3 }; int M = 2, K = 2; int N = arr.Length; if (SubarrayRepeatsKorMore( arr, N, M, K)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program for the above approach // Function to check if there exists // any subarray of length M repeating // at least K times consecutively function check(arr, M, K, ind) { // Iterate from i equal 0 to M for(let i = 0; i < M; i++) { // Iterate from j equals 1 to K for(let j = 1; j < K; j++) { // If elements at pos + i and // pos + i + j * M are not equal if (arr[ind + i] != arr[ind + i + j * M]) { return false; } } } return true; } // Function to check if a subarray repeats // at least K times consecutively or not function SubarrayRepeatsKorMore(arr, N, M, K) { // Iterate from ind equal 0 to M for(let ind = 0; ind <= N - M * K; ind++) { // Check if subarray arr[i, i + M] // repeats atleast K times or not if (check(arr, M, K, ind)) { return true; } } // Otherwise, return false return false; } // Driver Code let arr = [ 2, 1, 2, 1, 1, 1, 3 ]; let M = 2, K = 2; let N = arr.length; if (SubarrayRepeatsKorMore(arr, N, M, K)) { document.write("Yes"); } else{ document.write("No"); } // This code is contributed by subhammahato348 </script> |
Output:
Yes
Time Complexity: O(N*M*K)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using Two Pointers Technique. Follow the steps below to solve the problem:
- Initialize a variable, say count as 0.
- Traverse the given array arr[] over the range of indices [0, N – M] using a variable, say i, and perform the following steps:
- If the value of arr[i] is equal to arr[i + M], then increment count by 1, as there is a match in the subarray.
- Otherwise, update count to 0 as there is a break in the contiguous subarrays.
- If the value of count is M * (K – 1), then it means that there are K consecutively equal subarrays of length M. Therefore, print “Yes” and break out of the loop.
- After completing the above steps, if the count never becomes M * (K – 1), then print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to check if any subarray // of length M repeats at least // K times consecutively or not bool checkExists(int arr[], int N, int M, int K) { // Stores the required count // of repeated subarrays int count = 0; for (int i = 0; i < N - M; i++) { // Check if the next continuous // subarray has equal elements if (arr[i] == arr[i + M]) count++; else count = 0; // Check if K continuous subarray // of length M are found or not if (count == M * (K - 1)) return true; } // If no subarrays are found return false; } // Driver Code int main() { int arr[] = { 2, 1, 2, 1, 1, 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int M = 2, K = 2; if (checkExists(arr, N, M, K)) { cout << "Yes"; } else { cout << "No"; } return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to check if any subarray // of length M repeats at least // K times consecutively or not static boolean checkExists(int arr[], int N, int M, int K) { // Stores the required count // of repeated subarrays int count = 0; for(int i = 0; i < N - M; i++) { // Check if the next continuous // subarray has equal elements if (arr[i] == arr[i + M]) count++; else count = 0; // Check if K continuous subarray // of length M are found or not if (count == M * (K - 1)) return true; } // If no subarrays are found return false; } // Driver Code public static void main(String[] args) { int arr[] = { 2, 1, 2, 1, 1, 1, 3 }; int M = 2, K = 2; int N = arr.length; if (checkExists(arr, N, M, K)) { System.out.println("Yes"); } else { System.out.println("No"); } } } // This code is contributed by Kingash |
Python3
# Python3 program for the above approach # Function to check if any subarray # of length M repeats at least # K times consecutively or not def checkExists(arr, N, M, K): # Stores the required count # of repeated subarrays count = 0 for i in range(N - M): # Check if the next continuous # subarray has equal elements if (arr[i] == arr[i + M]): count += 1 else: count = 0 # Check if K continuous subarray # of length M are found or not if (count == M * (K - 1)): return True # If no subarrays are found return False # Driver Code if __name__ == '__main__': arr = [ 2, 1, 2, 1, 1, 1, 3 ] N = len(arr) M = 2 K = 2 if (checkExists(arr, N, M, K)): print("Yes") else: print("No") # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; class GFG{ // Function to check if any subarray // of length M repeats at least // K times consecutively or not public static bool checkExists(int []arr, int N, int M, int K) { // Stores the required count // of repeated subarrays int count = 0; for(int i = 0; i < N - M; i++) { // Check if the next continuous // subarray has equal elements if (arr[i] == arr[i + M]) count++; else count = 0; // Check if K continuous subarray // of length M are found or not if (count == M * (K - 1)) return true; } // If no subarrays are found return false; } // Driver Code public static void Main() { int []arr = { 2, 1, 2, 1, 1, 1, 3 }; int N = arr.Length; int M = 2, K = 2; if (checkExists(arr, N, M, K)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code is contributed by mohit kumar 29 |
Javascript
<script> // Javascript program for the above approach // Function to check if any subarray // of length M repeats at least // K times consecutively or not function checkExists(arr, N, M, K) { // Stores the required count // of repeated subarrays let count = 0; for (let i = 0; i < N - M; i++) { // Check if the next continuous // subarray has equal elements if (arr[i] == arr[i + M]) count++; else count = 0; // Check if K continuous subarray // of length M are found or not if (count == M * (K - 1)) return true; } // If no subarrays are found return false; } // Driver Code let arr = [ 2, 1, 2, 1, 1, 1, 3 ]; let N = arr.length; let M = 2, K = 2; if (checkExists(arr, N, M, K)) { document.write("Yes"); } else { document.write("No"); } </script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array
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!
