Duplica el primer elemento y mueve cero hasta el final.

Para una array dada de n enteros y suponga que ‘0’ es un número no válido y todos los demás son números válidos. Convierta la array de tal manera que si tanto el elemento actual como el siguiente son válidos y ambos tienen el mismo valor, duplique el valor actual y reemplace el siguiente número con 0. Después de la modificación, reorganice la array de modo que todos los 0 se desplacen al final. 
Ejemplos: 

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

Fuente: Experiencia de entrevista de IDC de Microsoft | Conjunto 150.

Enfoque: primero modifique la array como se mencionó, es decir, si el siguiente número válido es el mismo que el número actual, duplique su valor y reemplace el siguiente número con 0. 
Algoritmo para la modificación: 
 

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++

Después de modificar la array, mueva todos los ceros al final de la array .

// C++ implementation to rearrange the array
// elements after modification
#include <bits/stdc++.h>
 
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[0]);
 
    cout << "Original array: ";
    printArray(arr, n);
 
    modifyAndRearrangeArr(arr, n);
 
    cout << "\nModified array: ";
    printArray(arr, n);
 
    return 0;
}

// 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 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("\nModified array:",end=" ")
printArray(arr, n)
 
# This code is contributed by Smitha Dinesh Semwal

// 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

<script>
      // JavaScript implementation to rearrange the array
      // elements after modification
 
      // function which pushes all zeros to end of
      // an array.
      function pushZerosToEnd(arr, n)
      {
        // Count of non-zero elements
        var count = 0;
 
        // Traverse the array. If element encountered
        // is non-zero, then replace the element at
        // index 'count' with this element
        for (var 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
      function modifyAndRearrangeArr(arr, n)
      {
       
        // if 'arr[]' contains a single element
        // only
        if (n == 1) return;
 
        // traverse the array
        for (var 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
      function printArray(arr, n)
      {
        for (var i = 0; i < n; i++) document.write(arr[i] + " ");
      }
 
      // Driver program to test above
      var arr = [0, 2, 2, 2, 0, 6, 6, 0, 0, 8];
      var n = arr.length;
 
      document.write("Original array: ");
      printArray(arr, n);
 
      modifyAndRearrangeArr(arr, n);
      document.write("<br>");
      document.write("Modified array: ");
      printArray(arr, n);
       
      // This code is contributed by rdtank.
    </script>

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

Producción: 

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

Complejidad temporal: O(n).
Espacio Auxiliar: O(1)

Aproximación con cambios de cero eficientes:

Aunque la solución anterior es eficiente, podemos optimizarla aún más al cambiar los algoritmos cero al reducir el número de operaciones.

En los algoritmos de desplazamiento anteriores, escaneamos algunos elementos dos veces cuando establecemos el índice de conteo al último elemento de índice en cero.

Algoritmos de cambio de cero eficientes:

int lastSeenPositiveIndex = 0;
for( index = 0; index < n; index++)
{
    if(array[index] != 0)
    {
        swap(array[index], array[lastSeenPositiveIndex]);
        lastSeenPositiveIndex++;
    }
}

// Utility Function For Swapping Two Element Of An Array
void swap(int& a, int& b) { a = b + a - (b = a); }
 
// shift all zero to left side of an array
void shiftAllZeroToLeft(int array[], int n)
{
    // Maintain last index with positive value
    int lastSeenNonZero = 0;
 
    for (index = 0; index < n; index++)
    {
        // If Element is non-zero
        if (array[index] != 0)
        {
            // swap current index, with lastSeen non-zero
            swap(array[index], array[lastSeenNonZero]);
 
            // next element will be last seen non-zero
            lastSeenNonZero++;
        }
    }
}
 
// This snippet is contributed By: Faizanur Rahman

class GFG {
    // Function For Swapping Two Element Of An Array
    public static void swap(int[] A, int i, int j)
    {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
 
    // shift all zero to left side of an array
    static void shiftAllZeroToLeft(int array[], int n)
    {
        // Maintain last index with positive value
        int lastSeenNonZero = 0;
 
        for (int index = 0; index < n; index++) {
            // If Element is non-zero
            if (array[index] != 0) {
                // swap current index, with lastSeen
                // non-zero
                swap(array, array[index],
                     array[lastSeenNonZero]);
 
                // next element will be last seen non-zero
                lastSeenNonZero++;
            }
        }
    }
}
 
// This code is contributed By sam_2200

# Maintain last index with positive value
def shiftAllZeroToLeft(arr, n):
    lastSeenNonZero = 0
    for index in range(0, n):
       
        # If Element is non-zero
        if (array[index] != 0):
           
            # swap current index, with lastSeen
            # non-zero
            array[index], array[lastSeenNonZero] = array[lastSeenNonZero], array[index]
             
            # next element will be last seen non-zero
            lastSeenNonZero++
 
            # This code is contributed By sam_2200

using System;
class GFG
{
   
    // Function For Swapping Two Element Of An Array
    public static void swap(int[] A, int i, int j)
    {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
 
    // shift all zero to left side of an array
    static void shiftAllZeroToLeft(int[] array, int n)
    {
       
        // Maintain last index with positive value
        int lastSeenNonZero = 0;
 
        for (int index = 0; index < n; index++)
        {
           
            // If Element is non-zero
            if (array[index] != 0)
            {
               
                // swap current index, with lastSeen
                // non-zero
                swap(array, array[index],
                     array[lastSeenNonZero]);
 
                // next element will be last seen non-zero
                lastSeenNonZero++;
            }
        }
    }
}
 
// This code is contributed By Saurabh Jaiswal

<script>
 
    // Function For Swapping Two Element Of An Array
    function swap(A,i,j)
    {
        let temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
 
    // shift all zero to left side of an array
    function shiftAllZeroToLeft(array,n)
    {
        // Maintain last index with positive value
        let lastSeenNonZero = 0;
 
        for (let index = 0; index < n; index++) {
            // If Element is non-zero
            if (array[index] != 0) {
                // swap current index, with lastSeen
                // non-zero
                swap(array, array[index],
                    array[lastSeenNonZero]);
 
                // next element will be last seen non-zero
                lastSeenNonZero++;
            }
        }
    }
}
 
// This code is contributed by sravan kumar Gottumukkala
 
</script>

Complejidad temporal: O(n)
Espacio auxiliar: O(1)