Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Algorithm for Modification
2.2.
Implementation in Python
2.3.
Implementation in C++
2.4.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in Python
3.3.
Implementation in C++
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a pivot element in array partitioning?
4.2.
What are the limitations of using loops?
4.3.
What is a dynamic array and in which language is it possible?
5.
Conclusion
Last Updated: Mar 27, 2024

Double the first element and move zero to the end

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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)

 

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;
}

 

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 AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!

Previous article
Ada String
Next article
Design Parking System
Live masterclass