## Introduction

In this blog, we will look at the approach to replace two consecutive equal values with one greater value in an array.

Also read about, __kth largest element in an array__, and __Euclid GCD Algorithm__

### Problem Statement

**Given:** An array of integers of size â€˜nâ€™.

**Problem:** Replace two consecutive equal values with one greater value in an array. Make these changes until there are no consecutive elements with equal values.

### Sample Examples

```
Input : 6, 7, 7, 8, 3, 9, 9
Output : 6, 9, 3, 10
Explanation:
Step 1 - 6, 8, 8, 3, 9, 9 : In order to replace two consecutive equal values with one greater value, here we replace two consecutive equal values of 7 with a single value of 7 incremented by 1, which is 8.
Step 2 - 6, 9, 3, 10 : Similarly to replace two consecutive equal values with one greater value, here we replace two consecutive equal values of 9 with a single value of 10.
```

### Explanation with an example

Let us look at the following example demonstrating how we can replace two consecutive equal values with one greater value.

## Brute Force Approach

In this brute approach to replace two consecutive equal values with one greater value, first to replace every consecutive equal value of element, say â€˜xâ€™ with the next greater value of â€˜x+1â€™, till there are no remaining consecutive values in the array, we can use loops and conditional if-else statements for performing the brute force approach.

### Pseudocode

- Traverse the array from 0 to n and check if there are any consecutive equal values.
- If there is such a consecutive pair, then replace the first element with (the value of element + 1) and shift the elements in the array.
- Again traverse the array till all the consecutive equal values of elements are replaced with the next incremented value and perform the same operations.

### Implementation in Python

```
# Function to replace two consecutive equal values with one greater value
def ReplaceElement(ar, n):
index = 0 # To keep track of the index of elements
for i in range(0,n):
ar[index] = ar[i]
index = index + 1
# Check if the consecutive elements are equal or not
# If equal, replace with incremented value
while( index > 1 and ar[index-2] == ar[index-1]):
index = index - 1
ar[index-1] += 1
# Print array elements after modifications
for i in range(0, index):
print(ar[i])
# Main program
ar = [6, 3, 7, 7, 5, 5]
n = len(ar)
ReplaceElement( ar, n)
```

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
// Function to replace two consecutive equal values with one greater value
void ReplaceElements(int ar[], int n) {
int index = 0; // To keep track of the index of elements
for (int i = 0; i < n; i++) {
ar[index++] = ar[i];
while (index > 1 && ar[index - 2] == ar[index - 1]) {
index--;
ar[index - 1]++;
}
}
// To print array after modifications
for (int i = 0; i < index; i++)
cout << ar[i] << " ";
}
// Main Program
int main() {
int ar[] = { 6, 3, 7, 7, 5, 5 };
int n = sizeof(ar) / sizeof(int);
ReplaceElements(ar, n);
return 0;
}
```

**Output: **

`6 3 8 6`

### Complexity Analysis

**Time: Complexity**: In this approach to replace two consecutive equal values with one greater value, we have used nested loops from 1 to n to traverse over the given array, which means that we are iterating over every element of the array n times and again reiterating over the elements; therefore, the program's complexity will be O(n^{2}). During this implementation, the counter variable i is incremented or decremented by a constant value accordingly, so we assign the complexity of O(n^{2}).

**Space complexity:** O(1) as it is independent of the number of elements in the array. The algorithm takes constant space but the program has the space complexity of O(n).