Given an array arr[], the task is to find the minimum number of elements to be removed such that every element at an even index in the array is different from the next element and return the array after removing.
Examples:
Input: arr[] = {5, 6, 8, 8, 7, 7, 5}
Output: {5, 6, 8, 7, 7, 5}
Explanation: arr2 element and arr3 element were equal. so deleting one of themInput: A[] = {2, 2, 2}
Output: 2
Explanation: arr2 is equal to arr1 so removing arr2 now arr3 becomes arr2 again equal to arr1 hence removing it as well.
Approach: This can be solved with the following idea:
- The main idea is to add elements in an array and check if the current element we are adding is getting placed at an odd index (next to an even indexed element) and if it is so then it should not be equal to the last element at even index else discard the element. Add elements at odd index in the new array simply without any conditions to be checked.
- Take an empty vector of Integer and then iterate the given array arr from starting and add the current element to the new vector if the size of the vector is even (because in that case, we are definitely adding an element which will be at odd index in the new vector as already even a number of elements are already there in the vector and we don’t have conditions on elements at even index)
- Or if the current element is not equal to the last element in the vector (obviously there is no issue when the last element and the current element are not equal ).
Steps involved in the implementation of the above approach:
- Take a vector<int> which will store the final result
- Iterate through the given array from the starting
- Check if the size of the vector or if the current element is not equal to the last added element if so then, add the element to the vector
- Iterate through the vector and print the result.
Below is the implementation of the code:
C++
// C++ Implementation#include <bits/stdc++.h>using namespace std;// Function to find array after removing elementvoid validate(int arr[], int n){ vector<int> vec; for (int i = 0; i < n; i++) { // Checking the size of vec or the current // element not equal to the last added element if ((vec.size() % 2 == 0) or (vec.back() != arr[i])) { vec.push_back(arr[i]); } } // Printing the result for (auto x : vec) { cout << x << " "; } return;}// Driver codeint main(){ int arr[] = { 1, 3, 2, 2, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call validate(arr, n); return 0;} |
Java
/*package whatever // do not write package name here */import java.io.*;import java.util.ArrayList;class GFG { static void validate(int arr[], int n) { ArrayList<Integer> vec = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { // checking the size of vec or the current element not equal to the last added element if ((vec.size() % 2 == 0) || (vec.get(vec.size() - 1) != arr[i])) { vec.add(arr[i]); } } // printing the result for (int i = 0; i < vec.size(); i++) { System.out.print(vec.get(i) + " "); } } public static void main(String[] args) { int arr[] = { 1, 3, 2, 2, 5 }; int n = arr.length; validate(arr, n); }} |
Python3
def validate(arr, n): vec = [] for i in range(n): # Checking the size of vec or the current # element not equal to the last added element if (len(vec) % 2 == 0) or (vec[-1] != arr[i]): vec.append(arr[i]) # Printing the result for x in vec: print(x, end=' ') return# Driver codearr = [1, 3, 2, 2, 5]n = len(arr)# Function callvalidate(arr, n) |
C#
using System;using System.Collections.Generic;public class Program { // Function to find array after removing element public static void Validate(int[] arr, int n) { List<int> vec = new List<int>(); for (int i = 0; i < n; i++) { // Checking the size of vec or the current // element not equal to the last added element if ((vec.Count % 2 == 0) || (vec[vec.Count - 1] != arr[i])) { vec.Add(arr[i]); } } // Printing the result foreach(int x in vec) { Console.Write(x + " "); } } // Driver code public static void Main() { int[] arr = { 1, 3, 2, 2, 5 }; int n = arr.Length; // Function call Validate(arr, n); }} |
Javascript
// Function to find array after removing elementfunction validate(arr) { let vec = []; for (let i = 0; i < arr.length; i++) { // Checking the size of vec or the current // element not equal to the last added element if (vec.length % 2 === 0 || vec[vec.length - 1] !== arr[i]) { vec.push(arr[i]); } } // Printing the result console.log(vec.join(" "));}// Driver codeconst arr = [1, 3, 2, 2, 5];// Function callvalidate(arr);//this code is contributed by Tushar Rokade |
Output
1 3 2 5
Time Complexity: O(n)
Auxiliary Space: O(n), since n extra space has been taken.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
