Find number of clumps in an array in C++

In this tutorial, we are going to learn how to find the number of clumps in an array in C++. Here we will learn about the clumps in an array and algorithm to find the number of clumps. After that, we will see the C++ program for the same.

Clumps in an array

A clump is a group of two or more adjacent numbers or characters of the same value in the array.
Here, we have to count the total number of clumps present in the given array means the total number of groups having the same adjacent numbers.
For example :- arr ={1,2,3,3,3,4,5,5,6,7,8,9,9,9}
In the above example total no. of clumps are 3 i.e {3,3,3},{5,5} and {9,9,9}.

Algorithm

To find the no. of clumps in an array we have to traverse the whole array and check if arr[i]==arr[i+1] and increment the count variable. See the detailed algorithm below:-

Algorithm

  1. Initialize two variable count=0 and flag=0.
  2. Traverse the array and check that current element is equal to the next element i.e arr[i]==arr[i+1] and flag==0.
    • If step 2 is true, assign flag=1.
    • And increment count++.
  3. Now check the condition else if, current element is not equal to the next element i.e arr[i]!=arr[i+1]
    • If step 3 is true, assign flag=0.
  4. Repeat steps 2 and 3 until the given array is traversed.
  5. Return count.

C++ program to find the number of clumps in an array

So, here is the C++ implementation of the above algorithm:-

#include<bits/stdc++.h>
using namespace std; 

/*===============================================
FUNCTION TO COUNT NO. OF CLUMPS IN GIVEN ARRAY
================================================*/
int count_the_clumps(int arr[], int size)
{
    //Initializing variable flag and count 
   int count=0;
   int flag=0;
   //Traversing whole array 
    for(int i=0;i<size;i++)
    {
        //If current element is equal to next element
        //and flag==0, increment count & flag=1
        if(arr[i]==arr[i+1] && flag==0)
        {
            flag=1;
            count++;
        }
        //If current elemnet is not equal to next,flag=0
        else if(arr[i]!=arr[i+1])
        {
            flag=0;
        }
  }
  return count;
}

/*======================================
   MAIN FUNCTION
=======================================*/
int main() 
{ 
    //Initialising array
    int arr[]={1,2,3,3,3,4,5,5,6,7,8,9,9,9};
    //Finding size of the given array
    int size = sizeof(arr)/sizeof(arr[0]); 
    //Calling function to find clumps
    int ans=count_the_clumps(arr,size); 
    //Displaying Output
    cout<<"No. of Clumps in the given array: "<<ans<<endl;
    return 0; 
} 

Output:-

No. of Clumps in the given array: 3

Time Complexity: O(n)

 

From the output, we can say we implement the task successfully.

Thanks for reading this tutorial. I hope it helps you !!

Leave a Reply