## Introduction

In this blog, we will look at the approach to double the first element and move the zeros in the array to the end. We will also see if there can be multiple approaches to solve the problem or not, and if yes then we will also discuss the different approaches.

Also see, __kth largest element in an array__, and __Euclid GCD Algorithm__

### Problem Statement

**Given:** An array of n integers and assume that ‘0’ is an invalid number and all other numbers are valid.

**Problem:** Convert the given array such that if both current and next element are valid and both have the same value then, double the first element and replace the next number with 0. After the changes, rearrange the array in a way such that all 0’s are shifted to the end.

### Sample Examples

**Example 1:**

```
Input: ar[ ] = {0,0,5,5,0,8,0,15}
Output: 10 8 15 0 0 0 0 0
Explanation: Since 5 occurs consecutively, we double the first element with value of 5 first to make it 10 and mark the next 5, if any, to 0. Then all the zeros in the array are shifted to the end.
```

**Example 2:**

```
Input: ar[ ] = {0,0,1,1,1,0,0,7,7,0,6}
Output: 2 1 14 6 0 0 0 0 0 0 0
Explanation: First, consecutive 1’s are doubled to the value of 2 and the next 1 is changed to 0. Similarly, consecutive 7’s are doubled to the value of 14 and finally, all the 0’s are shifted to the end.
```

## Brute Force Approach

Firstly, in order to modify the given array, we search if the next valid number is similar to the current number,i.e., we look for consecutive numbers, then we double the first element’s value and replace the next number with 0. Finally, we shift all the 0’s to the end.

### Algorithm for Modification

```
# First check if the array is complete or not
if n == 1
return
# Now,run a loop till (n-2) index to check all the elements
for i = 0 to n-2
# Check if the element at i index is 0 or not and if the
# consecutive elements are the same.
# If element is not zero and consecutive,double the first element.
# Store 0 at (i+1) index to replace the second element.
if (ar[i] != 0) && (ar[i] == ar[i+1])
ar[i] = 2 * ar[i]
ar[i+1] = 0
i++
```

### Implementation in Python

```
# Program to double the first element and move zero to the end
def pushZerosToEnd(arr, n):
count = 0
for i in range(0, n):
if arr[i] != 0:
arr[count] = arr[i]
count+=1
while (count < n):
arr[count] = 0
count+=1
def modifyAndRearrangeArr(ar, n):
if n == 1:
return
for i in range(0, n - 1):
if (arr[i] != 0) and (arr[i] == arr[i + 1]):
arr[i] = 2 * arr[i]
arr[i + 1] = 0
i+=1
pushZerosToEnd(arr, n)
def printArray(arr, n):
for i in range(0, n):
print(arr[i])
# Main program
arr = [ 0, 1, 1, 1, 0, 0, 7, 7, 0, 6 ]
n = len(arr)
print("Original array:",end=" ")
printArray(arr, n)
modifyAndRearrangeArr(arr, n)
print("\nModified array:",end=" ")
printArray(arr, n)
```

### Implementation in C++

```
//Program to double the first element and move zero to the end
#include <bits/stdc++.h>
using namespace std;
// function which pushes all zeros to the end of an array.
void ShiftZeros(int ar[], int n)
{
// Count of non-zero elements
int count = 0;
// Run a loop to check if element encountered
// is non-zero, then replace the element at
// index 'count' with this element
for (int i = 0; i < n; i++)
if (ar[i] != 0)
// here count is incremented
ar[count++] = ar[i];
// Now all non-zero elements have been shifted
// to front and 'count' is set as index of
// first 0 element. Make all elements 0 from count
// to end.
while(count<n)
{
ar[count++] = 0 ;
}
}
// function to rearrange the array elements after changes
void ChangeArr(int ar[], int n)
{
// if 'ar[]' contains a single element only
if (n == 1)
return;
// traverse the array
for (int i = 0; i < n - 1; i++)
{
// if true, perform the required modification
if ((ar[i] != 0) && (ar[i] == ar[i + 1]))
{
// double current index value
ar[i] = 2 * ar[i];
// put 0 in the next index
ar[i + 1] = 0;
// increment by 1 so as to move two
// indexes ahead during loop iteration
i++;
}
}
// shift all the zeros at the end of 'arr[]'
ShiftZeros(ar, n);
}
// Print Function
void printArray(int ar[], int n)
{
for (int i = 0; i < n; i++)
cout << ar[i] << " ";
}
// Main program to test above code
int main()
{
int ar[] = { 0, 1, 1, 1, 0, 0, 7, 7, 0, 6 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "Given array: ";
printArray(ar, n);
ChangeArr(ar, n);
cout << "\nModified array: ";
printArray(ar, n);
return 0;
}
```

**Output:**

```
Input: 0 0 1 1 1 0 0 7 7 0 6
After modification: 2 1 14 6 0 0 0 0 0 0 0
```

### Complexity Analysis

**Time Complexity:** The approach consists of two loops, one for checking if there are consecutive elements or not and if yes then changing the first element with its double and making the next element 0. The other loop makes modifications in the complete array and shifts all 0’s to the end. During this implementation, the counter variable i is incremented or decremented by a constant value accordingly and so, we assign the time complexity of O(n).

**Space Complexity:** This program has O(n) space complexity, as it stores n values for the input.