Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Examples 
1.3.
Explanation with an example
2.
Brute Force Approach 
2.1.
Pseudocode 
2.2.
Implementation in Python 
2.3.
Implementation in C++
2.4.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.3.
Implementation in Java
3.4.
Complexity Analysis
4.
Frequently Asked Questions 
4.1.
What are nested loops?
4.2.
What is the difference between traversing an array and searching for specific elements?
4.3.
What is a quadratic complexity?
5.
Conclusion 
Last Updated: Mar 27, 2024
Easy

Replace two consecutive equal values with one greater value

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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 

  1. Traverse the array from 0 to n and check if there are any consecutive equal values.
  2. 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.
  3. 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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In this approach, we will use stack to make the program more efficient by using push and pop operations.

Pseudocode

The pseudocode is as follows:

  1. Push the first element onto the stack.
  2. Start traversing the array from i = 1 to n, and check if(arr[i] == stack.peek()),then pop the element and increment the popped element by 1. 
  3. Now again check the same condition and keep removing then incrementing the popped element till the condition is true. Finally push the element onto the stack.
  4. Else, push the element onto the stack.

Implementation in C++

// Program to replace two consecutive equal values with one greater
#include <bits/stdc++.h>

using namespace std;

void replace_con(int a[], int n) {
    stack < int > ss;
    int i;
    int current;

    for (i = 0; i < n; i++) {

        if (ss.empty() || ss.top() != a[i]) {
            ss.push(a[i]);
        } else {
            current = a[i];
            while (!ss.empty() && current == ss.top()) {
                current = ss.top() + 1;
                ss.pop();
            }
            ss.push(current);
        }
    }

    int b[ss.size()];
    i = 0;
    int m = ss.size();

    while (!ss.empty()) {

        b[i] = ss.top();
        i++;
        ss.pop();
    }

    for (i = m - 1; i >= 0; i--) {
        cout << b[i] << " ";
    }

    cout << endl;
}
int main() {
    int i;
    int n = 6;
    int ar[n] = { 6, 3, 7, 7, 5, 5 };

    replace_con(ar, n);

    return 0;
}

 

Implementation in Java

// Program to replace two consecutive equal values with one greater
import java.util.Stack;

class ReplaceConsEle {
    public static void main(String[] args) {

        ReplaceConsEle rce = new ReplaceConsEle();
        int ar[] = { 6, 3, 7, 7, 5, 5 };
        int n = ar.length;
        rce.replaceElements(ar, n);
    }

    private void replaceElements(int[] ar, int n) {
        Stack < Integer > stack = new Stack < > ();
        stack.push(ar[0]);

        int temp = 0;
        for (int i = 1; i < n; i++) {

            if (ar[i] == stack.peek()) {
                temp = ar[i];

                while (!stack.isEmpty() && stack.peek() == temp) {
                    temp = stack.pop();
                    temp++;
                }

                stack.push(temp);
            } else
                stack.push(ar[i]);
        }

        for (int ele: stack)
            System.err.print(ele + " ");

        System.out.println();
    }

}

 

Output: 

6 3 8 6 

 

Complexity Analysis

Time Complexity - We have traversed over n elements in the array and therefore, the time complexity is O(n).

Space Complexity - The auxiliary space is used for n elements and therefore, the space complexity is O(n).

Frequently Asked Questions 

What are nested loops?

A nested loop has one loop inside of another and is mostly used for working with two dimensions. 

What is the difference between traversing an array and searching for specific elements?

Traversing refers to iterating over the complete array and in case of searching, we iterate over the array until the element we are looking for is found. Searching may or may not be done till the end of the array.

What is a quadratic complexity?

O(n2) is known as the quadratic complexity and it represents the complexity of an algorithm, whose performance is proportional to the square of the size of the input elements.

Conclusion 

This article discussed the approach to replace two consecutive values with one greater value in an array. We have also implemented the pseudocode for the program in Python and Java and have understood the working of the algorithm with the help of an example.

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Design Parking System
Next article
Check If a Number is Not a Power of 2
Live masterclass