Given an array arr[] of size N of positive integers. The task is to rearrange the array after applying the conditions given below:
- If arr[i] and arr[i+1] are equal then multiply the ith (current) element with 2 and set the (i +1)th element to 0.
- After applying all the conditions move all zeros at the end of the array.
Examples:
Input: N = 6, arr[] = [1, 2, 2, 1, 1, 0]
Output: [1, 4, 2, 0, 0, 0]
Explanation: At i = 0: arr[0] and arr[1] are not the same, so we do nothing.
At i = 1: arr[1] and arr[2] are the same, so we multiply arr[1] with 2 and change its next element to 0.
array = [1, 4, 0, 1, 1, 0]
At i = 2: arr[2] and arr[3] are not the same, so we do nothing.
At i = 3: arr[3] and arr[4] are the same, so we multiply arr[3] with 2 and change its next element to
arr[] = [1, 4, 0, 2, 0, 0]
At i = 4: arr[4] and arr[5] are the same, so we multiply arr[4] with 2 and change its next element to 0.
arr[] = [1, 4, 0, 2, 0, 0]
After applying the above 2 conditions, shift all the 0’s to the right side of the array.
arr[]= [1, 4, 2, 0, 0, 0]Input: N =2, arr[] = [0, 1]
Output: [1, 0]
Explanation: At i = 0: arr[0] and arr[1] are not same, so we do nothing.
No conditions can be applied further, so we shift all 0’s to right.
arr[] = [1, 0]
Approach: Linear Iteration
The basic idea is to linearly iterate the array and check whether the conditions are satisfied or not and perform operations according to the conditions.
Illustration:
Consider an array arr[] = {1, 2, 2, 1, 1, 0};
At i = 0:
arr[0] and arr[1] are not the same, so we do nothing.At i = 1:
arr[1] and arr[2] are the same, so we multiply arr[1] with 2 and change its next element to 0.
arr[] = [1, 4, 0, 1, 1, 0]At i = 2:
arr[2] and arr[3] are not the same, so we do nothing.At i = 3:
arr[3] and arr[4] are the same, so we multiply arr[3] with 2 and change its next element to 0.
arr[]= [1, 4, 0, 2, 0, 0]At i = 4:
arr[4] and arr[5] are the same, so we multiply arr[4] with 2 and change it’s next element to 0.
arr[] = [1, 4, 0, 2, 0, 0]After applying the above 2 conditions, shift all the 0’s to right side of the array.
arr[] = [1, 4, 2, 0, 0, 0]
Follow the steps below to implement the above idea:
- Traverse through the given array from i = 0 to N-2.
- If the ith element is equal to the next element then,
- Multiply the current element with 2 arr[i]*2.
- Set next element arr[i]+1 with 0.
- Now right shift all the 0’s.
- Create a counter variable count to count the number of non-zero elements of the array.
- If arr[i] is not zero then just update the array with counter variable arr[count++] = arr[i].
- set all zeroes at the end of the array.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to shift all zeros to right side of arrayvoid rightShift(int arr[], int n){ int count = 0; for (int i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; } } while (count < n) { arr[count++] = 0; }}// Function to apply the given conditionsvoid applyConditions(int arr[], int n){ for (int i = 0; i < n - 1; i++) { // Condition 1 if (arr[i] == arr[i + 1]) { arr[i] = arr[i] * 2; arr[i + 1] = 0; } // Condition 2 else { continue; } } // Function Call rightShift(arr, n);}// Driver Codeint main(){ int arr[] = { 1, 2, 2, 1, 1, 0 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call applyConditions(arr, N); for (int i = 0; i < N; i++) { cout << arr[i] << " "; } return 0;}// This code is contributed by Tapesh(tapeshdua420) |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to apply the given conditions static void applyConditions(int[] arr, int n) { for (int i = 0; i < n - 1; i++) { // Condition 1 if (arr[i] == arr[i + 1]) { arr[i] = arr[i] * 2; arr[i + 1] = 0; } // Condition 2 else { continue; } } // Function Call rightShift(arr, n); } // Function to shift all zeros to right side of array static void rightShift(int[] arr, int n) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; } } while (count < n) { arr[count++] = 0; } } // Driver Code public static void main(String[] args) { int[] arr = { 1, 2, 2, 1, 1, 0 }; int N = arr.length; // Function Call applyConditions(arr, N); for (int i = 0; i < N; i++) { System.out.print(arr[i] + " "); } }} |
Python3
# Python code to implement the approach# Function to shift all zeros to right side of arraydef rightShift(arr, n): count = 0 for i in range(n): if (arr[i] != 0): arr[count] = arr[i] count += 1 while (count < n): arr[count] = 0 count += 1# Function to apply the given conditionsdef applyConditions(arr, n): for i in range(n - 1): # Condition 1 if (arr[i] == arr[i + 1]): arr[i] = arr[i] * 2 arr[i + 1] = 0 # Condition 2 else: continue # Function Call rightShift(arr, n)# Driver Codeif __name__ == '__main__': arr = [1, 2, 2, 1, 1, 0] N = len(arr) # Function Call applyConditions(arr, N) for i in range(N): print(arr[i], end=" ")# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approachusing System;public class GFG { // Function to apply the given conditions static void applyConditions(int[] arr, int n) { for (int i = 0; i < n - 1; i++) { // Condition 1 if (arr[i] == arr[i + 1]) { arr[i] = arr[i] * 2; arr[i + 1] = 0; } // Condition 2 else { continue; } } // Function Call rightShift(arr, n); } // Function to shift all zeros to right side of array static void rightShift(int[] arr, int n) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; } } while (count < n) { arr[count++] = 0; } } static public void Main() { // Code int[] arr = { 1, 2, 2, 1, 1, 0 }; int N = arr.Length; // Function Call applyConditions(arr, N); for (int i = 0; i < N; i++) { Console.Write(arr[i] + " "); } }}// This code is contributed by lokeshmvs21. |
Javascript
// JS code to implement the approach // Function to apply the given conditionsfunction applyConditions(arr, n) { for (let i = 0; i < n - 1; i++) { // Condition 1 if (arr[i] == arr[i + 1]) { arr[i] = arr[i] * 2; arr[i + 1] = 0; } // Condition 2 else { continue; } } // Function Call rightShift(arr, n); } // Function to shift all zeros to right side of arrayfunction rightShift(arr, n) { let count = 0; for (let i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; } } while (count < n) { arr[count++] = 0; } } let arr = [ 1, 2, 2, 1, 1, 0 ]; let N = arr.length; // Function Call applyConditions(arr, N); for (let i = 0; i < N; i++) { console.log(arr[i] + " "); }// This code is contributed by ksam24000. |
1 4 2 0 0 0
Time Complexity: O(N), because we are iterating the array two times.
Auxiliary Space: O(1)
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
