# Double the first element and move zero to end

Given an array of integers of size n. Assume ‘0’ as invalid number and all other as valid number. Convert the array in such a way that if next valid number is same as current number, double its value and replace the next number with 0. After the modification, rearrange the array such that all 0’s are shifted to the end.

Examples:

```Input : arr[] = {2, 2, 0, 4, 0, 8}
Output : 4 4 8 0 0 0

Input : arr[] = {0, 2, 2, 2, 0, 6, 6, 0, 0, 8}
Output :  4 2 12 8 0 0 0 0 0 0
```

Approach: First modify the array as mentioned, i.e., if next valid number is same as current number, double its value and replace the next number with 0.
Algorithm for Modification:

```1. if n == 1
2.     return
3. for i = 0 to n-2
4.     if (arr[i] != 0) && (arr[i] == arr[i+1])
5.         arr[i] = 2 * arr[i]
6.       arr[i+1] = 0
7.       i++
```

After modifying the array, Move all zeroes to the end of array.

## C++

 `// C++ implementation to rearrange the array  ` `// elements after modification ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// function which pushes all zeros to end of  ` `// an array. ` `void` `pushZerosToEnd(``int` `arr[], ``int` `n) ` `{ ` `    ``// Count of non-zero elements ` `    ``int` `count = 0; ` ` `  `    ``// Traverse the array. If element encountered ` `    ``// is non-zero, then replace the element at  ` `    ``// index 'count' with this element ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``if` `(arr[i] != 0) ` ` `  `            ``// here count is incremented ` `            ``arr[count++] = arr[i]; ` ` `  `    ``// Now all non-zero elements have been shifted ` `    ``// to front and 'count' is set as index of ` `    ``// first 0. Make all elements 0 from count ` `    ``// to end. ` `    ``while` `(count < n) ` `        ``arr[count++] = 0; ` `} ` ` `  `// function to rearrange the array elements ` `// after modification ` `void` `modifyAndRearrangeArr(``int` `arr[], ``int` `n) ` `{ ` `    ``// if 'arr[]' 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` `((arr[i] != 0) && (arr[i] == arr[i + 1])) { ` ` `  `            ``// double current index value ` `            ``arr[i] = 2 * arr[i]; ` ` `  `            ``// put 0 in the next index ` `            ``arr[i + 1] = 0; ` ` `  `            ``// increment by 1 so as to move two  ` `            ``// indexes ahead during loop iteration ` `            ``i++; ` `        ``} ` `    ``} ` ` `  `    ``// push all the zeros at the end of 'arr[]' ` `    ``pushZerosToEnd(arr, n); ` `} ` ` `  `// function to print the array elements ` `void` `printArray(``int` `arr[], ``int` `n) ` `{ ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``cout << arr[i] << ``" "``; ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `arr[] = { 0, 2, 2, 2, 0, 6, 6, 0, 0, 8 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` ` `  `    ``cout << ``"Original array: "``; ` `    ``printArray(arr, n); ` ` `  `    ``modifyAndRearrangeArr(arr, n); ` ` `  `    ``cout << ````" Modified array: "````; ` `    ``printArray(arr, n); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java implementation to rearrange the  ` `// array elements after modification ` `class` `GFG { ` ` `  `    ``// function which pushes all  ` `    ``// zeros to end of an array. ` `    ``static` `void` `pushZerosToEnd(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``// Count of non-zero elements ` `        ``int` `count = ``0``; ` ` `  `        ``// Traverse the array. If element  ` `        ``// encountered is non-zero, then ` `        ``// replace the element at index ` `        ``// 'count' with this element ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``if` `(arr[i] != ``0``) ` ` `  `                ``// here count is incremented ` `                ``arr[count++] = arr[i]; ` ` `  `        ``// Now all non-zero elements  ` `        ``// have been shifted to front and  ` `        ``// 'count' is set as index of first 0.  ` `        ``// Make all elements 0 from count to end. ` `        ``while` `(count < n) ` `            ``arr[count++] = ``0``; ` `    ``} ` ` `  `    ``// function to rearrange the array ` `    ``//  elements after modification ` `    ``static` `void` `modifyAndRearrangeArr(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``// if 'arr[]' 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` `((arr[i] != ``0``) && (arr[i] == arr[i + ``1``])) ` `            ``{ ` ` `  `                ``// double current index value ` `                ``arr[i] = ``2` `* arr[i]; ` ` `  `                ``// put 0 in the next index ` `                ``arr[i + ``1``] = ``0``; ` ` `  `                ``// increment by 1 so as to move two ` `                ``// indexes ahead during loop iteration ` `                ``i++; ` `            ``} ` `        ``} ` ` `  `        ``// push all the zeros at  ` `        ``// the end of 'arr[]' ` `        ``pushZerosToEnd(arr, n); ` `    ``} ` ` `  `    ``// function to print the array elements ` `    ``static` `void` `printArray(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``System.out.print(arr[i] + ``" "``); ` `        ``System.out.println(); ` `    ``} ` ` `  `    ``// Driver program to test above ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = { ``0``, ``2``, ``2``, ``2``, ``0``, ``6``, ``6``, ``0``, ``0``, ``8` `}; ` `        ``int` `n = arr.length; ` ` `  `        ``System.out.print(``"Original array: "``); ` `        ``printArray(arr, n); ` ` `  `        ``modifyAndRearrangeArr(arr, n); ` ` `  `        ``System.out.print(``"Modified array: "``); ` `        ``printArray(arr, n); ` `    ``} ` `} ` ` `  `// This code is contributed   ` `// by prerna saini `

## Python3

 `# Python3 implementation to rearrange  ` `# the array elements after modification ` ` `  `# function which pushes all zeros  ` `# to end of an array. ` `def` `pushZerosToEnd(arr, n): ` ` `  `    ``# Count of non-zero elements ` `    ``count ``=` `0` ` `  `    ``# Traverse the array. If element  ` `    ``# encountered is non-zero, then  ` `    ``# replace the element at index  ` `    ``# 'count' with this element ` `    ``for` `i ``in` `range``(``0``, n): ` `        ``if` `arr[i] !``=` `0``: ` ` `  `            ``# here count is incremented ` `            ``arr[count] ``=` `arr[i] ` `            ``count``+``=``1` ` `  `    ``# Now all non-zero elements have been  ` `    ``# shifted to front and 'count' is set ` `    ``# as index of first 0. Make all  ` `    ``# elements 0 from count to end. ` `    ``while` `(count < n): ` `        ``arr[count] ``=` `0` `        ``count``+``=``1` ` `  ` `  `# function to rearrange the array ` `# elements after modification ` `def` `modifyAndRearrangeArr(ar, n): ` ` `  `    ``# if 'arr[]' contains a single ` `    ``# element only ` `    ``if` `n ``=``=` `1``: ` `        ``return` ` `  `    ``# traverse the array ` `    ``for` `i ``in` `range``(``0``, n ``-` `1``): ` ` `  `        ``# if true, perform the required modification ` `        ``if` `(arr[i] !``=` `0``) ``and` `(arr[i] ``=``=` `arr[i ``+` `1``]): ` ` `  `            ``# double current index value ` `            ``arr[i] ``=` `2` `*` `arr[i] ` ` `  `            ``# put 0 in the next index ` `            ``arr[i ``+` `1``] ``=` `0` ` `  `            ``# increment by 1 so as to move two  ` `            ``# indexes ahead during loop iteration ` `            ``i``+``=``1` ` `  `     `  ` `  `    ``# push all the zeros at the end of 'arr[]' ` `    ``pushZerosToEnd(arr, n) ` ` `  ` `  `# function to print the array elements ` `def` `printArray(arr, n): ` ` `  `    ``for` `i ``in` `range``(``0``, n): ` `        ``print``(arr[i],end``=``" "``) ` ` `  ` `  `# Driver program to test above ` `arr ``=` `[ ``0``, ``2``, ``2``, ``2``, ``0``, ``6``, ``6``, ``0``, ``0``, ``8` `] ` `n ``=` `len``(arr)  ` ` `  `print``(``"Original array:"``,end``=``" "``) ` `printArray(arr, n) ` ` `  `modifyAndRearrangeArr(arr, n) ` ` `  `print``(````" Modified array:"````,end``=``" "``) ` `printArray(arr, n) ` ` `  `# This code is contributed by Smitha Dinesh Semwal `

## C#

 `// C# implementation to rearrange the ` `// array elements after modification ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// function which pushes all ` `    ``// zeros to end of an array. ` `    ``static` `void` `pushZerosToEnd(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``// Count of non-zero elements ` `        ``int` `count = 0; ` ` `  `        ``// Traverse the array. If element ` `        ``// encountered is non-zero, then ` `        ``// replace the element at index ` `        ``// 'count' with this element ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``if` `(arr[i] != 0) ` ` `  `                ``// here count is incremented ` `                ``arr[count++] = arr[i]; ` ` `  `        ``// Now all non-zero elements ` `        ``// have been shifted to front and ` `        ``// 'count' is set as index of first 0. ` `        ``// Make all elements 0 from count to end. ` `        ``while` `(count < n) ` `            ``arr[count++] = 0; ` `    ``} ` ` `  `    ``// function to rearrange the array ` `    ``// elements after modification ` `    ``static` `void` `modifyAndRearrangeArr(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``// if 'arr[]' 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` `((arr[i] != 0) && (arr[i] == arr[i + 1])) { ` ` `  `                ``// double current index value ` `                ``arr[i] = 2 * arr[i]; ` ` `  `                ``// put 0 in the next index ` `                ``arr[i + 1] = 0; ` ` `  `                ``// increment by 1 so as to move two ` `                ``// indexes ahead during loop iteration ` `                ``i++; ` `            ``} ` `        ``} ` ` `  `        ``// push all the zeros at ` `        ``// the end of 'arr[]' ` `        ``pushZerosToEnd(arr, n); ` `    ``} ` ` `  `    ``// function to print the array elements ` `    ``static` `void` `printArray(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``Console.Write(arr[i] + ``" "``); ` `        ``Console.WriteLine(); ` `    ``} ` ` `  `    ``// Driver program to test above ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] arr = { 0, 2, 2, 2, 0, 6, 6, 0, 0, 8 }; ` `        ``int` `n = arr.Length; ` ` `  `        ``Console.Write(``"Original array: "``); ` `        ``printArray(arr, n); ` ` `  `        ``modifyAndRearrangeArr(arr, n); ` ` `  `        ``Console.Write(``"Modified array: "``); ` `        ``printArray(arr, n); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

Output:

```Original array: 0 2 2 2 0 6 6 0 0 8
Modified array: 4 2 12 8 0 0 0 0 0 0
```

Time Complexity: O(n).