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(n2). During this implementation, the counter variable i is incremented or decremented by a constant value accordingly, so we assign the complexity of O(n2).
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).
569+ registered 
