Modify Array by modifying adjacent equal elements

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 i^th (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:
array[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 array[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 array[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 array[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 i^th 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.

Java

import java.io.*;

class GFG {

static void applyConditions(int[] arr, int n)

{

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

if (arr[i] == arr[i + 1]) {

arr[i] = arr[i] * 2;

arr[i + 1] = 0;

}

else {

continue;

}

rightShift(arr, n);

}

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;

}

public static void main(String[] args)

{

int[] arr = { 1, 2, 2, 1, 1, 0 };

int N = arr.length;

applyConditions(arr, N);

for (int i = 0; i < N; i++) {

System.out.print(arr[i] + " ");

}

Time Complexity: O(N), because we are iterating the array two times.
Auxiliary Space: O(1)

Related Articles:

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 i^th (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:
array[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 array[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 array[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 array[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 i^th 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.

Java

import java.io.*;

class GFG {

static void applyConditions(int[] arr, int n)

{

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

if (arr[i] == arr[i + 1]) {

arr[i] = arr[i] * 2;

arr[i + 1] = 0;

}

else {

continue;

}

rightShift(arr, n);

}

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;

}

public static void main(String[] args)

{

int[] arr = { 1, 2, 2, 1, 1, 0 };

int N = arr.length;

applyConditions(arr, N);

for (int i = 0; i < N; i++) {

System.out.print(arr[i] + " ");

}

Time Complexity: O(N), because we are iterating the array two times.
Auxiliary Space: O(1)

Related Articles:

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – admin@technoblender.com. The content will be deleted within 24 hours.

Modify Array by modifying adjacent equal elements

Java

Java

Related Posts