Given an array arr[] of N integers, the task is to count the number of clumps in the given array.
Clump is defined as a series of 2 or more adjacent elements of the same value.
Examples:
Input: arr[] = { 13, 15, 66, 66, 37, 8, 8, 11, 52 };
Output: 2
Explanation:
There are two clumps in the given array {66, 66} and {8, 8}.
Input: arr[] = {1, 2, 1, 4, 3, 2}
Output: 0
Explanation:
There are no clumps in the given array.
Approach: In order to solve the problem, we need to follow the following steps:
- Traverse through the array and check for any occurrence of same element on two consecutive indices.
- For any such occurrence, loop until a different number occurs.
- Increase the count of clumps by 1 only after execution of step 2. If the entire array isn’t traversed yet, repeat the above steps for the following elements.
- Print the final count of clumps after entire array traversal.
Below is the implementation of the above approach:
C++
// C++ program to calculate // the number of clumps in // an array #include <bits/stdc++.h> using namespace std; // Function to count the number of // clumps in the given array arr[] int countClumps( int arr[], int N) { // Initialise count of clumps as 0 int clumps = 0; // Traverse the arr[] for ( int i = 0; i < N - 1; i++) { int flag = 0; // Whenever a sequence of same // value is encountered while (arr[i] == arr[i + 1]) { flag = 1; i++; } if (flag) clumps++; } // Return the count of clumps return clumps; } // Driver Code int main() { // Given array int arr[] = { 13, 15, 66, 66, 66, 37, 37, 8, 8, 11, 11 }; // length of the given array arr[] int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << countClumps(arr, N) << '\n' ; return 0; } |
Java
// Java program for the above approach class Test { // Given array arr[] static int arr[] = { 13 , 15 , 66 , 66 , 66 , 37 , 37 , 8 , 8 , 11 , 11 }; // Function to count the number of // clumps in the given array arr[] static int countClumps() { int l = arr.length; // Initialise count of clumps as 0 int clumps = 0 ; // Traverse the arr[] for ( int i = 0 ; i < l - 1 ; i++) { int flag = 0 ; // Whenever a sequence of same // value is encountered while (i < l - 1 && arr[i] == arr[i + 1 ]) { flag = 1 ; i++; } if (flag == 1 ) clumps++; } // Return the count of clumps return clumps; } // Driver Code public static void main(String[] args) { // Function Call System.out.println(countClumps()); } } |
Python3
# Python3 program to calculate # the number of clumps in # an array # Function to count the number of # clumps in the given array arr[] def countClumps(arr, N): # Initialise count of clumps as 0 clumps = 0 # Traverse the arr[] i = 0 while (i < N - 1 ): flag = 0 # Whenever a sequence of same # value is encountered while (i + 1 < N and arr[i] = = arr[i + 1 ]): flag = 1 i + = 1 if (flag): clumps + = 1 i + = 1 # Return the count of clumps return clumps # Driver Code # Given array arr = [ 13 , 15 , 66 , 66 , 66 , 37 , 37 , 8 , 8 , 11 , 11 ] # length of the given array arr[] N = len (arr) # Function Call print (countClumps(arr, N)) # This code is contributed by yatin |
C#
// C# program for the above approach using System; class GFG{ // Given array arr[] static int []arr = { 13, 15, 66, 66, 66, 37, 37, 8, 8, 11, 11 }; // Function to count the number of // clumps in the given array arr[] static int countClumps() { int l = arr.Length; // Initialise count of clumps as 0 int clumps = 0; // Traverse the arr[] for ( int i = 0; i < l - 1; i++) { int flag = 0; // Whenever a sequence of same // value is encountered while (i < l - 1 && arr[i] == arr[i + 1]) { flag = 1; i++; } if (flag == 1) clumps++; } // Return the count of clumps return clumps; } // Driver Code public static void Main() { // Function Call Console.WriteLine(countClumps()); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program to calculate // the number of clumps in // an array // Function to count the number of // clumps in the given array arr[] function countClumps(arr, N) { // Initialise count of clumps as 0 let clumps = 0; // Traverse the arr[] for (let i = 0; i < N - 1; i++) { let flag = 0; // Whenever a sequence of same // value is encountered while (arr[i] == arr[i + 1]) { flag = 1; i++; } if (flag) clumps++; } // Return the count of clumps return clumps; } // Given array let arr = [ 13, 15, 66, 66, 66, 37, 37, 8, 8, 11, 11 ]; // length of the given array arr[] let N = arr.length; // Function Call document.write(countClumps(arr, N)); </script> |
4
Time Complexity: O(N), where N is the number of elements in the given array.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!