You are not logged in. Please login at www.codechef.com to post your questions!

×

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 :)

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

asked 22 Sep '17, 06:13

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%


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

#include <iostream>

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[i]==0)

        {

            a[i]=a[j];

            a[j]=0;

            cnt++;

            i++;

            j--;

        }

        else

        {

            i++;

        }

    }

}

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

cout<<a[i]<<" ";

cout<<"\ncount : "<<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 .

link

answered 22 Sep '17, 12:53

trashmaster's gravatar image

2★trashmaster
98619
accept rate: 12%

edited 22 Sep '17, 12:58

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,664
×862
×95
×45
×7

question asked: 22 Sep '17, 06:13

question was seen: 376 times

last updated: 22 Sep '17, 12:58