Double the first element and move zero to end

Difficulty Level Medium
Frequently asked in Microsoft Zoho
ArrayViews 1825

Problem Statement

Suppose you have an array of integers. Here “0” is not a number which is considered as an input. It is not valid input here. The problem “Double the first element and move zero to end” asks to rearrange the array in such a way if a number other than 0 is found and the next number of that is the same number as it is then double the number and marked the next number as 0. At last push all the zeroes at the end.

Example

arr[] = {3, 3, 5, 0, 1, 0, 0, 1, 0}
6 5 1 1 0 0 0 0 0

Explanation: Since 3 is the number which occurs consecutively, so we double the 3 first to make it 6 and mark the next 3 as 0. And also all the zeroes have been shifted to last.x

Algorithm for Double the first element and move zero to end

1. Traverse the array from 0 to n-1(inclusively).
2. Check if arr[i] is not equal to 0 and arr[i]==arr[i+1](next value is same as current value).
  1. If true, then make the current value twice of the self.
  2. Update next element as 0 and do i++.
3. Traverse the array from i = 0 to n-1(step of shifting all the zeroes to the end).
  1. Check if arr[i] != 0.
    1. Arr[count]=arr[i] and do count++.
4. From the traversal of till count is less than n.
  1. Arr[count]=0 and do count++.
5. Print the array.

Explanation

Given an array to rearrange it in a given manner. We have asked to change the next number if the current number is the same as the next number. The change is that we have to double the current number. And mark the next number as 0 if the given condition satisfies. After this modification, we have to shift all the zeroes at the last of the array which we have made or which already are present in an array. Then the output is supposed to be returned.

Traverse the array from 0 to n – 1. Check if each of the value is not equal to 0. Because we are not allowed to make any changes to 0’s values. And check if the current element is equal to the next element as arr[i] = = arr[i+1]. We have taken n-1 as a last point of traversal because we are searching for the next number to the current number. So if we go for n as the last element to be searched for, we will get the null pointer exception. If the given conditions are satisfied then we pick the current element and double it of the current value and update the next value to 0. We should do this for all values of the array.

Now shift all the values as 0 to the last. For this traverse the array again, and check if the value is not equal to, then shifts it towards the left, after shifting all the values to the left we have an index of lastly shifted value, from that count we will be going for a loop and from that count to the value of n, we will update all the values as 0. At last print the array.

Double the first element and move zero to end

Code

C++ code for Double the first element and move zero to end problem

#include<iostream>

using namespace std;

void shiftZeroAtLast(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;
}
void arrayModification(int arr[], int n)
{
    if (n == 1)
        return;
    for (int i = 0; i < n - 1; i++)
    {
        if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
        {
            arr[i] = 2 * arr[i];

            arr[i + 1] = 0;

            i++;
        }
    }
    shiftZeroAtLast(arr, n);
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {3,3,5,0,1,0,0,1,0};
    int n = sizeof(arr) / sizeof(arr[0]);

    arrayModification(arr, n);

    cout << "Modified array: ";
    printArray(arr, n);

    return 0;
}

Modified array: 6 5 1 1 0 0 0 0 0

Java code for Double the first element and move zero to end problem

class arrayRearrange
{
    public static void shiftZeroAtLast(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 arrayModification(int arr[], int n)
    {
        if (n == 1)
            return;

        for (int i = 0; i < n - 1; i++)
        {
            if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
            {
                arr[i] = 2 * arr[i];

                arr[i + 1] = 0;

                i++;
            }
        }
        shiftZeroAtLast(arr, n);
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = {3,3,5,0,1,0,0,1,0};
        int n = arr.length;


        arrayModification(arr, n);

        System.out.print("Modified array: ");
        printArray(arr, n);
    }
}

Modified array: 6 5 1 1 0 0 0 0 0

Complexity Analysis

Time Complexity

O(N) where “N” is the number of elements in the array. We have simply traversed the array twice which makes the algorithm to run in linear time.

Space Complexity

The algorithm requires O(1) extra space but the program takes O(N) total space to store the input.

Translate »