Non-zero Elements Problem

Hello friends recently my friend went for Facebook interview and the following question was asked and the interviewer kept on drilling down for more optimized solution that too with in-place algorithm . So I would like to have a discussion here to arrive at an optimized solution :slight_smile:

Write an algorithm that brings all nonzero elements to the left of the array, and returns the number of nonzero elements.

Example input: [ 1, 0, 2, 0, 0, 3, 4 ]
Example output: 4

[1, 4, 2, 3, 0, 0, 0]

The algorithm should operate in place, i.e. shouldn’t create a new array.
The order of nonzero elements does not matter

The order of non-zero elements doesn’t matter . It makes the question easier .

#include

using namespace std;

int main()

{

int a[7]={1, 0, 2, 0, 0, 3, 4 },cnt=0,temp,i,j;

for(int i=0,j=6;i<=j;)

{

	if(a[j]==0)

	{

		cnt++;

		j--;

		continue;

	}

	else 

	{

		if(a*==0)

		{

			a*=a[j];

			a[j]=0;

			cnt++;

			i++;

			j--;

		}

		else

		{

			i++;

		}

	}

}

for(int i=0;i<7;i++)

cout<<a*<<" ";

cout<<"

count : "<<cnt;

return 0;

}

You just have to maintain a pointer from last and one from beginning to swap the non-zero elements from the end with the zero elements in the beginning .

It would be really helpful if you tell how your friend got the opportunity to interview with facebook .

EDIT I am counting the zero elements here . You can find the non-zero elements by subtracting the cnt from total elements .