CLB_CodingChallenge_6_5_2018_V2

/*Problem description
Given N natural number(s), separate 0's and bring them to the left side of the containers.
Time Complexity  : O(n)
Memory Complexity: O(1)
*/

#include <iostream>
using namespace std;

int main() {
    int* storage;           //Use dynamic allocated array
    int numOfNum;           //Number of input(s)

    //Take in the input and display it
    cin >> numOfNum;
    storage = new int[numOfNum];
    for (int indx = 0; indx < numOfNum; indx++) {
        cin >> storage[indx];
    }
    //Display the initial list
    cout << "Your initial list: ";
    for (int indx = 0; indx < numOfNum; indx++) {
        cout << storage[indx] << " ";
    }
    cout << endl;

    //Go from the last index to the first one, shift all the non zero to the right most position
    //  (next to another right most or end of the array)
    int lastZeroPos = -1;   //The index of the last 0 position
    //First, find the position of the last 0
    for (lastZeroPos = numOfNum - 1; lastZeroPos >= 0 && storage[lastZeroPos] != 0; lastZeroPos--);
    if (lastZeroPos <= 0) {
        //Nothing to shift
        cout << "Your list doesn't need to be shifted!" << endl;
    } else {
        //Then shift
        for (int indx = lastZeroPos - 1; indx >= 0; indx--) {
            //If we encounter something non-zero then...
            if (storage[indx] != 0) {
                //Swap!
                storage[lastZeroPos--] = storage[indx];
                storage[indx] = 0;
            }
        }
        //And, finally, re-display
        cout << "Your shifted list: ";
        for (int indx = 0; indx < numOfNum; indx++) {
            cout << storage[indx] << " ";
        }
        cout << endl;
    }

    delete[] storage;                   //Delete after you play!
    return 0;
}