Replace the element with the greatest element on the right side of an array in C++
In this tutorial, we will learn to replace the element with the greatest element on the right side in C++. Also, we have given an array and we have to replace the element with the greatest element.
NOTE: Moreover, we will replace the last element with -1. Because there is nothing left after that element.
For Example:
- Given array: { 17, 4, 18, 3, 1, 5, -2 }
- Replace the element with which is the largest element in the right.
- Output will be: { 18, 18, 5, 5, 5, -2, -1 }
Approach:
Simple Method:
- Firstly, iterate through two for loops.
- The outer loop will go through elements one by one starting from left to right.
- The inner loop will find the greatest element among them.
- Finally, the outer loop will replace the current element with the greatest element.
- The time complexity: O(n^2)
Efficient method:
- Firstly, iterate through only one for loop. This will definitely reduce the time complexity of our code.
- We will start from the rightmost element and will move towards the right.
- Every time we will keep a record of the greatest element.
- Simultaneously, we will replace the element with the greatest element.
- Time complexity: O(n)
You may also like:
Find and replace in a sentence or string in C++
Replace the element with the greatest element on the right side of an array in C++
Implementation:
// C++ Program to replace #include<iostream> #include <bits/stdc++.h> using namespace std; // Function to replace element with greatest void replacegreatest(int arr[], int ab) { // Initialize the next greatest element int maxin_righ = arr[ab-1]; // The greatest element for rightmost arr[ab-1] = -1; // Replace all other elements for(int i = ab-2; i >= 0; i--) { // store element in a variable int x = arr[i]; // Replace element with greatest arr[i] = maxin_righ; // Update the greatest element if satisfied if(maxin_righ < x) maxin_righ = x; } } // printing array void printm(int arr[], int ab) { for (int i = 0; i < ab; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = {17, 4, 18, 3, 1, 5, -2}; int ab = sizeof(arr)/sizeof(arr[0]); replacegreatest (arr, ab); printm (arr, ab); return 0; }
Output Explanation:
INPUT: {17, 4, 18, 3, 1, 5, -2 } OUTPUT: {18, 18, 5, 5, 5, -2, -1}
Leave a Reply