Double the first element and move zero to the end

Optimized Approach

For optimization, we can try to make the shifting of 0’s at the end positions of the array more efficient. For that, we can scan some of the elements twice when we set the count index to the index of the last element to zero.

Pseudocode

1. Declare a variable for storing the index of the last seen non-zero element and store the value 0 in it.
2. Run a loop till n (size of the array) and increment index i by 1.
3. Check if the element at index i is 0 or not and if yes, swap the element at i index with the element at the last positive seen index.
4. Increment the counter for storing last seen positive indices by 1.

Implementation in Python

# Program to double the first element and move zero to the end
def shiftAllZeroToLeft(arr, n):
    lastSeenNonZero = 0
    for index in range(0, n):
       
        # If Element is non-zero
        if (arr[index] != 0):
           
            # swap current index, with last seen non-zero index
            arr[index], arr[lastSeenNonZero] = arr[lastSeenNonZero], arr[index]
             
            # next element will be last seen non-zero
            lastSeenNonZero+=1
 
 
# function to rearrange the array
# elements after modification
def modifyAndRearrangeArr(arr, 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[]'
    shiftAllZeroToLeft(arr, n)
 
 
# function to print the array elements
def printArray(arr, n):
 
    for i in range(0, n):
        print(arr[i])
 
 
# Driver program to test above
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)

You can also try this code with Online Python Compiler

Run Code

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 end of
// an array.
void swap(int& a, int& b) 
{ 
    a = b + a - (b = a); 
}

void shiftAllZeroToLeft(int arr[], int n)
{
    // Maintain last index with positive value
    int lastSeenNonZero = 0;
 
    for (int index = 0; index < n; index++)
    {
        // If Element is non-zero
        if (arr[index] != 0)
        {
            // swap current index, with lastSeen non-zero
            swap(arr[index], arr[lastSeenNonZero]);
 
            // next element will be last seen non-zero
            lastSeenNonZero++;
        }
    }
}

 
// 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[]'
    shiftAllZeroToLeft(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, 1, 1, 1, 0, 0, 7, 7, 0, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << "Original array: ";
    printArray(arr, n);
 
    modifyAndRearrangeArr(arr, n);
 
    cout << "\nModified array: ";
    printArray(arr, n);
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

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: In this approach, the time complexity is O(n) because we traverse over n elements in the array.

Space Complexity: The space complexity for this approach is O(1) because the auxiliary space used is constant.

Frequently Asked Questions

What is a pivot element in array partitioning?

The pivot element is the chosen element according to the program condition around which we partition the array into subarrays. The pivot element can be chosen at random by the programmer or it can be calculated using a given condition.

What are the limitations of using loops?

Sometimes, we can face the problem of infinite loops, where we get the same answer over and over if the condition for breaking out of the loop is not carefully used. We can use break, continue, if-else statements to efficiently break out of the loop and execute the desired code segment.

What is a dynamic array and in which language is it possible?

We can use a dynamic array in Java as it is a variable size list data structure and it allocates memory at run time using the heap.

Conclusion

In this article, we have discussed a brute force based approach to double an element in the array if consecutive and move all zeros to the end. 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!