×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

Double the first element and move zero to end

C++ implementation to double the first element and move zero to end.
Submitted by Vikneshwar GK, on March 11, 2022

Consider an integer array, of size n. 0 is considered as an invalid integer whereas other numbers are valid integers. The task at hand is to iterate the array and check whether the current element is valid and its value is the same as the next element. If true, double the current element and replace the next element with 0. Finally, rearrange the array in such a way that all the zeros are placed at the end of the array.

Example

Input:
array[]= {2, 4, 0, 3, 3, 5, 8, 8, 0, 6}

Output:
array[] = {2, 4, 6, 5, 16, 6, 0, 0, 0, 0} 

Input:
array[]= {1, 2, 2, 4, 4}

Output:
array[] = {1, 4, 8, 0, 0}

Solution

This is a simple yet efficient method that involves iterating through the array and finding the elements that have the same value as its next element and that is not zero. If true, then double the current element and replace its next element with zero. Finally, iterate the array again and place the zero at the end of the array.

Algorithm for moving zeros to the end of the array:

  • Iterate the array
  • Use an index called count to assign non-zero elements in the array
  • If the element is not zero, then assign it to the array and increment the count
  • Again, iterate the through from count to the length of the array and assign zero

C++ Implementation

#include <bits/stdc++.h>

using namespace std;

// Function to push the zeros
// to the end of the array
void moveZerosToEnd(int array[], int length)
{
    // index to store non-zero elements
    int count = 0;

    // iterate the array
    for (int i = 0; i < length; i++)

        // if the element is not zero
        if (array[i] != 0)
            array[count++] = array[i];

    // assign zero to the remaining positions
    while (count < length)
        array[count++] = 0;
}

// function to double the element
// based on the conditions
void rearrangeArray(int array[], int length)
{
    // if the array has only one element
    if (length == 1)
        return;

    // traverse the array
    for (int i = 0; i < length - 1; i++) {

        // element not equal to zero
        // element is same as its next element
        if ((array[i] != 0) && (array[i] == array[i + 1])) {

            // double current index value
            array[i] = 2 * array[i];

            // assign zero to next element
            array[i + 1] = 0;

            // increment the array to one position
            // because the next element is zero
            i++;
        }
    }

    // call function to push the zeros
    moveZerosToEnd(array, length);
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Main function
int main()
{
    int array[100], N, k;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }
    
    rearrangeArray(array, N);
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1: 2
Enter element 2: 4
Enter element 3: 0
Enter element 4: 3
Enter element 5: 3
Enter element 6: 5
Enter element 7: 8
Enter element 8: 8
Enter element 9: 0
Enter element 10: 6
2 4 6 5 16 6 0 0 0 0

Time Complexity: O(n), where n is the length of the array.


Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.