Given an array arr[] of length N, the task is to find the count of non-overlapping subarrays of size K such that the alternate elements are equal.
Examples:
Input: arr[] = {2, 4, 2, 7}, K = 3
Output: 1
Explanation: Given subarray {2, 4, 2} is a valid array because the elements in even position(index no.0 and 2) are equal. Hence the count of the subarrays with size K = 3 is 1.Input: arr[] = {5, 2, 5, 2, 3, 9, 7, 9, 7}, K = 4
Output: 2
Explanation: Subarray {5, 2, 5, 2} and {9, 7, 9, 7} are valid subarrays because the elements in even position(index no.0 and 2) and odd positions(index no.1 and 3) are equal. Hence the count of the subarrays with size K = 4 is 2.
Approach: Implement the idea below to solve the problem
Initially find all the non-overlapping subarrays where alternate elements are equal. Comparing the lengths of each such subarray with K, we can find out how many valid subarrays of size K can be extracted from each of those.
Follow the below steps to implement the idea:
- Initialize t = 2 in starting and c = 0, to maintain the count of subarrays.
- Iterate over the array from index 2.
- Whenever we found arr[i] = arr[i-2], increment t by 1.
- When t gets equal to K, increase c by 1 and reset t = 0.
- If the length of the given array arr[] is less than 2, see the value of K and return the output accordingly.
- After iterating over the array, return c as the count subarrays.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <iostream>using namespace std;// Function to find the count of subarraysint fun(int arr[], int k, int n){ // For checking the length of array if (n <= 2) { if (k == 1) { return n; } else if (k == 2) { return 1; } else { return 0; } } int t = 2; int c = 0; // Loop through the array from 2 to arr.length for (int i = 2; i < n; i++) { // For checking the array elements at odd and // even index if (arr[i] == arr[i - 2]) { t = t + 1; } else { t = 2; } // check whether current size equals k if (t == k) { // Increment the count by 1 c = c + 1; t = 0; } } return c;}int main() { int arr[] = { 5, 2, 5, 2, 5, 2, 5, 2, 3, 9, 7, 9, 7 }; int K = 4; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << fun(arr, K, n) << endl; return 0;}// This code is contributed by lokesh. |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find the cound of subarrays static int fun(int[] arr, int k) { // For checking the length of array if (arr.length <= 2) { if (k == 1) { return arr.length; } else if (k == 2) { return 1; } else { return 0; } } int t = 2; int c = 0; // Loop through the array from 2 to arr.length for (int i = 2; i < arr.length; i++) { // For checking the array elements at odd and // even index if (arr[i] == arr[i - 2]) { t = t + 1; } else { t = 2; } // check whether current size equals k if (t == k) { // Increment the count by 1 c = c + 1; t = 0; } } return c; } public static void main(String[] args) { int[] arr = { 5, 2, 5, 2, 5, 2, 5, 2, 3, 9, 7, 9, 7 }; int K = 4; // Function call System.out.print(fun(arr, K)); }}// This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach# Function to find the count of subarraysdef fun(arr, k): # For checking the length of array if len(arr) <= 2: if k == 1: return len(arr) elif k == 2: return 1 else: return 0 else: # For storing current subarray t = 2 c = 0 # Loop through the array from 2 to len(arr) for i in range(2, len(arr)): # For checking the array elements at # odd and even index if arr[i] == arr[i-2]: t = t + 1 else: t = 2 # check whether current size # equals k if t == k: # Increment the count by 1 c += 1 t = 0 return c# Driver codeif __name__ == '__main__': arr = [5, 2, 5, 2, 5, 2, 5, 2, 3, 9, 7, 9, 7] K = 4 # Function call print(fun(arr, K)) |
C#
// C# code to implement the approachusing System;class GFG {// Function to find the cound of subarraysstatic int fun(int[] arr, int k){ // For checking the length of array if (arr.Length <= 2) { if (k == 1) { return arr.Length; } else if (k == 2) { return 1; } else { return 0; } } int t = 2; int c = 0; // Loop through the array from 2 to arr.length for (int i = 2; i < arr.Length; i++) { // For checking the array elements at odd and // even index if (arr[i] == arr[i - 2]) { t = t + 1; } else { t = 2; } // check whether current size equals k if (t == k) { // Increment the count by 1 c = c + 1; t = 0; } } return c;}static public void Main (){ int[] arr= { 5, 2, 5, 2, 5, 2, 5, 2, 3, 9, 7, 9, 7 }; int K = 4; // Function call Console.Write(fun(arr, K));}}// This code is contributed by Pushpesh Raj. |
Javascript
// javascript code to implement the approach// Function to find the count of subarraysfunction fun(arr, k, n){ // For checking the length of array if (n <= 2) { if (k == 1) { return n; } else if (k == 2) { return 1; } else { return 0; } } let t = 2; let c = 0; // Loop through the array from 2 to arr.length for (let i = 2; i < n; i++) { // For checking the array elements at odd and // even index if (arr[i] == arr[i - 2]) { t = t + 1; } else { t = 2; } // check whether current size equals k if (t == k) { // Increment the count by 1 c = c + 1; t = 0; } } return c;}let arr = [ 5, 2, 5, 2, 5, 2, 5, 2, 3, 9, 7, 9, 7 ]; let K = 4; let n = arr.length; // Function call console.log(fun(arr, K, n)); // This code is contributed by garg28harsh. |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
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!
Share your thoughts in the comments
