## Facebook Interview Question Software Engineer / Developers

• 0

Push all the zero's of a given array to the end of the array. In place only. Ex 1,2,0,4,0,0,8 becomes 1,2,4,8,0,0,0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
25
of 25 vote

C version O(n):

#define size 10

int arr[size] = {0, 0, 1, 2, 0, 4, 0, 0 ,8 ,9};
int pos = 0, i, count_zero;

for(i = 0; i <= size-1; i++) {
if(arr[i] != 0) {
arr[pos] = arr[i];
pos++;
}
}

for(i = size; i >= pos; i--)
arr[i] = 0;

Comment hidden because of low score. Click to expand.
0

A minor correction to the above code is to initialize i to (size-1) instead of size in the second for loop above.

Comment hidden because of low score. Click to expand.
0

void PushZeros(int* arr, int len)
{
int dst = 0;
int src = 0;
while(src < len)
{
if(arr[src])
arr[dst++] = arr[src++];
else
src++;
}
while(dst < src)
arr[dst++] = 0;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is an implementation with O(N) time complexity and O(1) storage.

inline void swap_ints(int dat[], int idx1, int idx2)
{
dat[idx1] = dat[idx1] ^ dat[idx2];
dat[idx2] = dat[idx1] ^ dat[idx2];
dat[idx1] = dat[idx1] ^ dat[idx2];
}

void group_zeros(int dat[], int count)
{
int i;
int zidx = count; // Initially set to a non-valid value

for(i = count - 1; i >= 0; i--) {
if (0 == dat[i] ){
if (count == zidx )
zidx = i;
}
else { // the current item is not a zero
if (zidx != count) { // if we had a hole in between
swap_ints(dat, zidx, i);
zidx--; // Decrement to next index, since it is the next hole
}
}
}
}

Comment hidden because of low score. Click to expand.
0

i think ur code does the opposite, it brings all the 0's to the left, while they should be brought to the right side.

Comment hidden because of low score. Click to expand.
0

Thanks for noting that, hitman. I just somehow missed that. Anyway, below is the implementation required. Anyway, the idea in this algorithm is just using a single index of the last position where the zero was encountered.
Below is the implementation for groupping zeros to right:

void group_zeros_right(int dat[], int count)
{
int i;
int zidx = count; // Initially set to a non-valid value

for(i = 0; i < count; i++) {
if (0 == dat[i] ){
if (count == zidx )
zidx = i;
}
else { // the current item is not a zero
if (zidx != count) { // if we had a hole in between
swap_ints(dat, zidx, i);
zidx++; // Increment to next index, since it is the next hole
}
}
}

}

Comment hidden because of low score. Click to expand.
0

Thanks for noting that, hitman. I just somehow missed that. Anyway, below is the implementation required. Anyway, the idea in this algorithm is just using a single index of the last position where the zero was encountered.
Below is the implementation for groupping zeros to right:

void group_zeros_right(int dat[], int count)
{
int i;
int zidx = count; // Initially set to a non-valid value

for(i = 0; i < count; i++) {
if (0 == dat[i] ){
if (count == zidx )
zidx = i;
}
else { // the current item is not a zero
if (zidx != count) { // if we had a hole in between
swap_ints(dat, zidx, i);
zidx++; // Increment to next index, since it is the next hole
}
}
}

}

Comment hidden because of low score. Click to expand.
1
of 3 vote

The code that works !!! Time complexity- 0(n).

#include<stdio.h>
#include<conio.h>
#define size 11
using namespace std;
int main()
{
int arr[size] = {1,9,9,4,0,0,2,7,0,6,7};
int current;
for(int j=0; j<size-1;j++)
{
if(arr[j]==0)
{
current=j;
break;
}}
int pos = current;
while( current <size )
{
if( arr[current] != 0 && current != pos )
{
arr[pos] = arr[current];
++pos;
}
++current;
}
while( pos<size)
{
arr[pos] = 0;
++pos;
}
for(int i=0;i<size;i++)
printf("%d",arr[i]);
getch();
return 0;
}

Comment hidden because of low score. Click to expand.
0

V nice and easy solution.. definitely O(n)

Comment hidden because of low score. Click to expand.
0

V nice and easy solution.. definitely O(n)

Comment hidden because of low score. Click to expand.
1
of 1 vote

void PushZero(int* pArray, int arraySize)
{
if (pArray == NULL) return;

int firstZeroIndex = 0;
while (firstZeroIndex < arraySize)
{
if (pArray[firstZeroIndex] == 0) break;
else firstZeroIndex++;
}

if (firstZeroIndex == arraySize) return;

int zeroIndex = firstZeroIndex;
for (int index = firstZeroIndex + 1; index < arraySize; index++)
{
if (pArray[index] != 0)
{
pArray[zeroIndex] = pArray[index];
pArray[index] = 0;
zeroIndex++;
}
}
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

Python Version O(n):

arr = [0, 0, 1, 2, 0, 4, 0, 0 ,8 ,9]
pos = 0

for i in range(len(arr)):
if arr[i] != 0:
arr[pos] = arr[i]
pos += 1

for i in reversed(range(pos, len(arr))):
arr[i] = 0

Comment hidden because of low score. Click to expand.
1
of 1 vote

public class Runner {
public static void main(String[] args)  {
int[] array = {1,2,0,4,0,0,8,0,0,4,2,1,5 };

shiftZeros(array, 0, array.length-1);

StringBuilder builder = new StringBuilder();
for(int i : array) {
builder.append(i);
builder.append(" ");
}
System.out.println(builder.toString());
}

public static void shiftZeros(int[] array, int begin ,int end) {
if(begin > end) {
return;
}

while(array[begin] != 0) {
begin++;
}

shiftArray(array, begin, end);

if(array[begin] == 0) {
shiftZeros(array,begin, end-1);
} else {
shiftZeros(array, begin+1, end);
}
}

public static void shiftArray(int[] array, int begin, int end) {
while(begin < end) {
array[begin] = array[begin+1];
begin++;
}
array[end] = 0;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#define SIZE 7
int tab[SIZE]={ 1,0,2,0,0,3,4};

void f(void)
{
int swapped, i, j, temp;
swapped=1;
i=0;
j=0;
while(swapped)
{
swapped=0;
while((i<SIZE)&&(j<SIZE))
{
while((tab[i]==0)&&(i<SIZE))
i++;
while((tab[j]!=0)&&(j<SIZE))
j++;
if((i<SIZE)&&(j<SIZE))
{
temp = tab[i];
tab[i] = tab[j];
tab[j] = temp;
swapped=1;
}
}
}
}

void main()
{
int i;
f();
for(i=0; i<SIZE ; i++)
{
printf("\n %d: %d", i, tab[i]);
}
exit(000);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void EndZero(int arr[], int size){

if(arr==NULL) return;
int l=0;
int r=size-1;
while(l<r){
while(arr[r]==0) r--;
while(arr[l]!=0) l++;

if(l<r && arr[l] == 0)
{
arr[l++]=arr[r];
arr[r--]=0;
}
}

}

Comment hidden because of low score. Click to expand.
0

This is fast, but the order of non-zero elements will be broken

Comment hidden because of low score. Click to expand.
0

This is fast, but the order of non-zero elements will be broken, I think you have to work from the head of the array to maintain the order.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#define SIZE 10
int main(){

int array = { 2, 3, 0, 0, 7, 0, 2, 6, 4, 7};
int newArray[SIZE];

int i, j=0;
for(i=0;i<SIZE;i++){
if(array[i]!=0){
newArray[j]=array[i];
j++;
}
}

for(i=j; i<SIZE; i++){
newArray[i]=0;
}
}

Comment hidden because of low score. Click to expand.
0

Yes, but this is not in place.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my answer to this question:

basicalgos.blogspot.com/2012/03/21-push-all-zeros-of-given-array-to-end.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

void set_end_zero(int arr[] ,int size)
{
int i = 0 ,j = 0;
while (j < size){
while (i < size && arr[i] != 0) ++i;
j = i + 1;
while (j < size && arr[j] == 0) ++j;
if (j < size){
arr[i] = arr[j];
arr[j] = 0;
}
++i;
++j;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

// Driver program to test above function
int main()
{
int arr[]= {0,8,9,0,0,5};
int size=sizeof(arr)/sizeof(int);

int i;

int j=-1;
for(i=0;i<size;i++)
{
if(arr[i]!=0)
{
j++;
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}

for(i=0;i<size;i++)
printf(" %d ", arr[i]);
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#define MAX 10
void shift_zero(int x[],int n);
int main()
{
int i=0,j=0,len=0,num[MAX];
printf("Enter length:\t");
scanf("%d",&len);
printf("length=%d\n\n",len);
for(i=0;i<len;i++)
{
scanf("%d",&num[i]);
}

for(j=0;j<len;j++)
printf("%d",num[j]);
shift_zero(num,len);
printf("\nNumber after shifting 0s:\n");
for(j=0;j<len;j++)
printf("%d",num[j]);
getch();
}

void shift_zero(int x[],int n)
{
int i=0,count0=0,p=0,temp=0;

for(i=0;i<n;i++)
{
if(x[i]==0)
{
if(temp==0)
{
p=i;
temp=1;
}
count0 ++;
continue;
}
if(temp==1)
{
x[i-count0]=x[i];
}
}
for(i=n-count0;i<n;i++)
x[i]=0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

An effective solution, in case all the integers are not negative, just multiply the array by -1 and then quick sort in ascending order.
Then multiply the array by -i again :)

Comment hidden because of low score. Click to expand.
0

In best case It takes (2*N + N*logN ) time.
Moreover, the initial order of the non-zero values will be broken, which may not be the intent of the interview question if you sort the elements in the array.

Comment hidden because of low score. Click to expand.
0

The output sample is sorted except all zeros on the right

Comment hidden because of low score. Click to expand.
0

public static void push(int [] array){
int temp;
for (int i=0,j=array.length-1;i<j;++i){
if (array[i]==0){
while(array[j]==0&&j>i){
j--;
}
System.out.println(array[j]);
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]={1,2,0,4,0,0,8};

int n=arr.length-1;
int left=n;

for(int i=n;i>=0;i--)
{
if(arr[i]==0)
{
int temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
left--;
}
}
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");

}

}

Comment hidden because of low score. Click to expand.
0

order of sequence is not maintained

Comment hidden because of low score. Click to expand.
0

order of sequence is not maintained

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]={1,2,0,4,0,0,8};

int n=arr.length-1;
int left=n;

for(int i=n;i>=0;i--)
{
if(arr[i]==0)
{
int temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
left--;
}
}
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]={1,2,0,4,0,0,8};

int n=arr.length-1;
int left=n;

for(int i=n;i>=0;i--)
{
if(arr[i]==0)
{
int temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
left--;
}
}
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]={1,2,0,4,0,0,8};

int n=arr.length-1;
int left=n;

for(int i=n;i>=0;i--)
{
if(arr[i]==0)
{
int temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
left--;
}
}
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");

}

}

Comment hidden because of low score. Click to expand.
0

as per the question you have to push zero to end only.. not to break the sequence.. try a[] = {0,0,4,2,0,6,0,9,0,0} with this in ur code.

Comment hidden because of low score. Click to expand.
0

as per the question you have to push zero to end only.. not to break the sequence.. try a[] = {0,0,4,2,0,6,0,9,0,0} with this in your code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int a[] = {1, 2, 0 , 4, 0 , 0 , 8 , 6 , 7 , 0 , 3 , 0};
int i , j;
i = 0;
j = 11;

while(i<j)
{
if(a[i] != 0)
i++;
else if(a[i] == 0 && a[j] != 0)
swap(&a[i] , &a[j]);
if(a[j] == 0)
j--;

}
for(i = 0;i<12;i++)
printf("%d", a[i]);

getch();
return 0;

}

swap(); a helper function..

Comment hidden because of low score. Click to expand.
0
of 0 vote

#define ARRAY_SIZE 10
int _tmain(int argc, _TCHAR* argv[])
{
int arr[ARRAY_SIZE] = {2, 3, 0, 5, 0, 3, 1, 0, 0, 1};

int j = ARRAY_SIZE - 1;

for(int i = 0; i < j; ++i)
{
if(arr[i] == 0)
{
while(arr[j] == 0)
{
--j;
}

arr[i] = arr[j];
arr[j] = 0;
}
}

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

this Question asked to me in Microsoft written :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic: Traverse the Array and replace [first zero] with [first non-zero after first zero]
1, 2, 0 , 4, 0 , 0 , 8 , 6 , 7 , 0 , 3 , 0 -----> 1,2,4,0,0,0,8,6,7,0,3,0
keep Applying this rule till the end

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

bool should_swap(int left, int right) {
return left == 0 && right != 0;
}

void print(int *a, int n) {
for(int i = 0; i < n; ++i) {
std::cout << a[i] << ' ';
}
std::cout << std::endl;
}

void move_zeros(int *a, int n) {
if(!a || !n) {
return;
}
for(int i = 0; i < n; ++i) {
for(int j = n - 1; j > i; --j) {
if(should_swap(a[j - 1], a[j])) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
}

int main() {
int a[] = {1,0,2,0,3,0,0};
int n = sizeof(a) / sizeof(int);
print(a, n);
move_zeros(a, n);
print(a, n);
return (0);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

JAVA version.
pointer i at the last non-zero position.
pointer j at the first zero position.
exchange and increment both to next valid position.

public class PushZeroToEnd {
public static void swap(int[]arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = new int[]{1,2,0,4,0,0,8};
int i = 0;
while(arr[i] != 0) {
i++;
}
for(int j = i; j < arr.length && i < arr.length; j++) {
if(arr[j] != 0 && i < j) {
swap(arr, i, j);
while(arr[i] != 0)
i++;
}
}
System.out.println();
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int* moveZero(int *src, int size)
{
int zero = 0;
while(zero < size && src[zero] != 0)
zero++;
for(int i = zero + 1; i < size; ++i)
{
if(src[i] != 0)
{
int tmp = src[i];
src[i] = 0;
src[zero++] = tmp;
}
}
return src;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int* moveZero(int *src, int size)
{
int zero = 0;
while(zero < size && src[zero] != 0)
zero++;
for(int i = zero + 1; i < size; ++i)
{
if(src[i] != 0)
{
int tmp = src[i];
src[i] = 0;
src[zero++] = tmp;
}
}
return src;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

need the non 0 elements be sorted ? or the example is a coincidence. we can push all non zero elements in a stack also counting number of 0. then print 0 from reverse in array then pop elements in array right to left

Comment hidden because of low score. Click to expand.
0
of 0 vote

To use constant space algorithm. keep 2 pointers. move left to right. P1 points to 0 and P2 points to non zero element next to P1. swap P1 and P2. P1++ and then move P2 till u find another non-zero element. O(n) time, O(1) space

Comment hidden because of low score. Click to expand.
0

But the order of non-zero is not maintained.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] zeros(int[] a, int val)
{
if (a == null)
throw new Exception();

if (a.Length == 1)
return a;

int index = a.Length - 1;
while (a[index] == val)
index--;

for (int i = 0; i < index; i++)
{
if (a[i] == val)
{
int temp = a[index];
a[index] = a[i];
a[i] = temp;

index--;
}
}

return a;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Perl version

#!/usr/local/bin/perl

my @array = (100,0,0,100,0,0,0,100);

\$j=0;
for(\$i=0;\$i<(\$#array );\$i++){

if((\$array[\$j] eq 0) and (\$array[\$i+1] ne 0)){
\$array[\$j]=\$array[\$i+1];
\$array[\$i+1]=0;
\$j++;
print "swap took place \n";
}elsif(\$array[\$j] ne 0){
\$j++;
}
}

print "\n";
foreach \$var(@array){
print \$var . "\t";
}
print "\n";

Comment hidden because of low score. Click to expand.
0
of 0 vote

Perl version

#!/usr/local/bin/perl

my @array = (100,0,0,100,0,0,0,100);

\$j=0;
for(\$i=0;\$i<(\$#array );\$i++){

if((\$array[\$j] eq 0) and (\$array[\$i+1] ne 0)){
\$array[\$j]=\$array[\$i+1];
\$array[\$i+1]=0;
\$j++;
print "swap took place \n";
}elsif(\$array[\$j] ne 0){
\$j++;
}
}

print "\n";
foreach \$var(@array){
print \$var . "\t";
}
print "\n";

Comment hidden because of low score. Click to expand.
0
of 0 vote

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<iostream>
using namespace std;

int main()
{
int a[] = {1,2,0,0,4,0,8};
int i = 0, j = 0, t;
while (i < 7 && j < 7) {
if (a[i] != 0) i++;
if (a[j] == 0 || j <= i) j++;
if (j > i && a[j] != 0) {
t = a[i];
a[i++] = a[j];
a[j++] = t;
}
}
for (int i = 0;i<7; i++)
cout<<a[i]<<" ";
cout<<endl;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
main()
{
int a[20],i,k,n,j;

printf("no. of elements:");
scanf("%d",&n);

printf("enter elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);

for(i=0;i<n;i++)
{
for(j=0;j<n;j++){
if(a[j]==0)
{
for(k=j;k<(n-1);k++)
a[k]=a[k+1];

a[n-1]=0;
}
}
}

for(i=0;i<n;i++)
printf("%d ",a[i]);

getch();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

According to question all values should be in ascending order and push the zero to the end...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
// printf("Hello world!\n");
int i, j, x;
int arr[7] = {1, 2, 0, 4, 0, 0, 8};
int arr1[7];
for(i = 0; i < 7; i++)
{
for(j = (i + 1); j < 7; j++)
{
if(arr[i] > arr[j])
{
x = arr[i];
arr[i] = arr[j];
arr[j] = x;
}
else
{

}
}

}

for(i = 0; i < 7; i++)
{
printf("The arr[%d] = %d \n", i, arr[i] ); // 0 0 0 1 2 4 8
}
for(i = 0, j = 0; i < 7 ; i++)
{
if(arr[i] != 0)
{
arr1[j] = (arr[i]); //<< i)/pow(2, i);
j++;
}

}
for(i = j; i < 7; i++, j++)
{
arr1[j] = 0;
}
for(i = 0; i < 7; i++)
{
printf("The arr1[%d] = %d \n", i, arr1[i] ); //1 2 4 8 0 0 0
}

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

int main (){
int a[7] = {1,2,0,4,0,0,8};
int count1 = 0;

for(int i = 0; i < 7; i++)
{
if(a[i] != 0)
{
a[count1] = a[i];
count1++;
}
}

for(int k = count1; k < 7; k++)
a[k] = 0;

//Print it out
for(int i = 0; i < 7; i++)
printf("%d ",a[i]);

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void
zeroes_to_end(int *a, size_t l) {
int i, lz;
for(i=0, lz=-1; i<l; i++) {
if (a[i] == 0 && lz == -1) lz = i;
if (a[i] != 0 && lz != -1) {
a[lz++] = a[i];
a[i] = 0;
}
}
}

Comment hidden because of low score. Click to expand.
0

O(N), in place and move only the numbers that need to be moved.
'lz' (last zero) should really be 'fz' (first zero), as it points to the first zero in the array.

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n), in place in C#

public static void PushZerosToEnd(ref int[] input)
{
//Keep track of the zero indices
int[] zeroIndices = new int[input.Length];
//Number of actual zeros at any point of time
int numZeros=0;
//Index of the zero that currently needs replacing
int numZeroReplaced=0;
for (int i = 0; i < input.Length;i++)
{
//If the current number is a zero, then keep track of its index
if (input[i] == 0)
{
zeroIndices[numZeros++] = i;
}
else
{
//If its not zero, check if some zero needs replacing
if (numZeros > 0)
{
//Replacing the first zero that needs replacing with this number
input[zeroIndices[numZeroReplaced++]] = input[i];
//Add this index on, since it can now be replaced
zeroIndices[numZeros++] = i;
//Just in case we dont end up replacing it, make it a zero
input[i] = 0;
}

}
if (i >= input.Length - numZeros)
{
//The last numZero indices should contain 0 anyway
input[i] = 0;
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0; i<n; i++)
{
if(a[i]==0)
{
int newi = i+1;
while(newi<n && a[newi] ==0) newi++;
if(newi<n){a[i] = a[newi]; a[newi] = 0;}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

\$data= array(1,2,0,0,4,5,0,7,8,0,0);
\$i=0;\$j=0;
foreach(\$data as \$value){
if(\$value !=0){
\$data[\$i]=\$data[\$j];
\$i++;
}
\$j++;
}
for(\$i; \$i<sizeof(\$data);\$i++){
\$data[\$i]=0;
}
foreach(\$data as \$value){
echo \$value . ",";
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[size] = {0, 0, 1, 2, 0, 4, 0, 0 ,8 ,9};
int start = 0;
int end = 0;

for(int i=0; i<size; i++)
{
if(arr[i] == 0)
{
end++;
}

if (arr[i] != 0)
{
arr[start]=arr[i];
arr[i] = 0;
start++;
end++;
}
}

Comment hidden because of low score. Click to expand.
0

your code doesn't work with case;

int[] array = new int [] { 1,2,0,4,0,0,8,0,0,4,2,1,5 };

Comment hidden because of low score. Click to expand.
0
of 0 vote

a somewhat complex approach -- still O(n) since each element is touched only once

void push_zeros(int *a, int n)
{
int s=-1,e=-2;
for(int i=0;i<n;++i)
{
if(a[i]==0)
{
if(e+1!=i) s=i;
while(a[i]==0 && i<n) ++i;
if(i==n) break;
//where zeros end
swap(a[s],a[i]);
s+=1;
e=i;
}
else
{
swap(a[s],a[i]);
s+=1;
e=i;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simplies, O(n), one for:

var ints = new[]{0,1,2,3,4,0,6};

int k = 0;

for(int i = 0; i<ints.Length; ++i)
{
if (ints[i] != 0)
{
ints[k] = ints[i];
if (k < i) ints[i] = 0;
++k;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n), one for-cycle:

var ints = new[]{0,1,2,3,4,0,6};
int k = 0;
for(int i = 0; i<ints.Length; ++i)
{
if (ints[i] != 0)
{
ints[k] = ints[i];
if (k < i) ints[i] = 0;
++k;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is not a difficult problem with the array in order ignoring all the zeros.

Comment hidden because of low score. Click to expand.
0
of 0 vote

move from left to write in the array, shifting the non zero elements when encounter a zero.
Keep count of 0s.
at the end just write out the zeros.

Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

/*
@param array<integer> input array
return array<integer> result, put 0s in the end of that array
*/
function moveZero (\$input){
foreach(\$input as \$index=>\$i){
if(\$i === 0 ){
array_push(\$input , \$i);
unset(\$input[\$index]);

}
}
return \$input;

}

print_r(moveZero(array(1,2,0,0,3,0,4)));

?>

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] PushZero(int[] arr)
{
int startZero = -1;
int endNumber = -1;

for(int i=0; i<arr.Length; i++)
{
if(arr[i] == 0 && startZero == -1)
{
startZero = i;
}
else if (arr[i] != 0)
{
endNumber++;

if (startZero != -1)
{
arr[startZero] = arr[i];
arr[i] = 0;
endNumber = startZero;
startZero = endNumber + 1;
}

}
}
return arr;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] PushZero(int[] arr)
{
int startZero = -1;
int endNumber = -1;

for(int i=0; i<arr.Length; i++)
{
if(arr[i] == 0 && startZero == -1)
{
startZero = i;
}
else if (arr[i] != 0)
{
endNumber++;

if (startZero != -1)
{
arr[startZero] = arr[i];
arr[i] = 0;
endNumber = startZero;
startZero = endNumber + 1;
}

}
}
return arr;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int postIndex =0;
for(int j=0;j<=size;j++)
{
if(a[j]!=0)
{
int temp=a[j];
a[j]=a[postIndex];
a[postIndex]=temp;
postIndex++;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

You all are making this easy thing very complicated.

#include<stdio.h>
#include<conio.h>
main()
{
int arr[10]={1,0,3,5,0,8,6,0,9,0};
int count=0,i;

for(i=1;i<=10;i++)
{
if(arr[i]!=0)
printf("%d",arr[i]);
else
count++;
}
for(i=1;i<=count;i++)
printf("0");

getch();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

package my.work;
public class Sort {

public static void main(String[] args) {
int arr[]={1,2,0,4,0,0,8,2,-2,234,22,0,1,0};
int j=0;
int len=arr.length;
for(int i=0;i<len;i++)
{
if(arr[i]!=0)
{
arr[j]=arr[i];
j++;
}
}
int nonzerosare=j;
for(int z=nonzerosare;z<len;z++){
arr[z]=0;
}
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
void swap(int*,int*);
int main()
{
int a[]={1, 2, 3};
int i=0;
int k;
int size=sizeof(a)/sizeof(a[0]);
do
{
while(a[i]!=0)
i++;
k=i+1;
while(a[k]==0&&k<size)
k++;
if(k==size)
break;
else
{
swap(&a[i],&a[k]);
i++;
}
}while(i<size);
cout<<"New array is "<<endl;
for(int j=0;j<size;j++)
{
cout<<a[j]<<'\t';
}

return 0;
}

void swap(int*a,int*b)
{
int t;
t=*a;
*a=*b;
*b=t;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
// Preparing random input
int input[] = new int[5];
Random r = new Random();
for(int i=0;i<5;i++){
input[i] = r.nextInt(10);
if(input[i] > 4)
input[i] = 0;
}
//int input[] = {0,2,2,2,1};
for(int i=0;i<5;i++){
System.out.print(input[i]+" ");
}
System.out.println("\n");

int j = 0,temp;
// Logic for pushing all zeros in place.
// If current element is 0 then, look for next non zero element and then swap with it.
// Worst case performance - O(n*n)
/*for(int i=0;i<input.length-1;i++){
if(input[i] == 0){
j = i + 1;
while(input[j] == 0 && j<input.length-1){
j++;
}
// Exchange
if(input[j] != 0){
temp = input[i];
input[i] = input[j];
input[j] = temp;
}
//
}
}*/
//
// O(n) logic. First find first zeroIndex.
// now swap ZeroIndex with first nonZero index. "then increment zeroIndex"
while(input[j] != 0){
j++;
}
int zeroIndex = j;
for(int i=zeroIndex;i<input.length;i++){
if(input[i] == 0){
//zeroIndex = i;
}
else{
//swap
temp = input[i];
input[i] = input[zeroIndex];
input[zeroIndex] = temp;
zeroIndex++;
}
}
for(int i=0;i<5;i++){
System.out.print(input[i]+" ");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int i=0,zero=0;
for(;i<inputArray.length;)

{
if(inputArray[i]==0)
{
i++;

}
else
{
int t=inputArray[i];
inputArray[i]=0;
inputArray[zero]=t;
zero++;
i++;

}
}

for(int j : inputArray)
System.out.println(j);

Comment hidden because of low score. Click to expand.
0
of 0 vote

Pseudo code with O(n)
(Lemme know if it's wrong!)

int pos=0;

for (int i=0; i<arr.length; i++)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, pressed enter prematurely in the last comment.

int pos=0;

for (int i=0; i<arr.length; i++)
{
if(arr[i]!=0)
{
arr[pos]=arr[i];
pos++;
}
}
for (pos ; pos <arr.length, pos++)
{arr[pos]=0;}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Partition algorithm:

void separate(int *a,int size)
{
int i,j;
i=0,j=size-1;

while(i<j)
{
while(a[i]) i++;
while(!a[j])j--;

if(i<j)
{
swap(&a[i],&a[j]);
i++;j--;
}
}

for(i=0;i<size;i++)
printf("%d ",a[i]);
}

Complete code: ideone.com/WHj6K

Comment hidden because of low score. Click to expand.
0
of 0 vote

#import<stdio.h>

int main()
{
int a[] = {1,2,0,3,0,4,0,5,0};
size_t len = sizeof(a)/sizeof(int);
int index0 = 0;
int indexN = 0;
for(int i = 0; i < len; i++)
printf("%d \t", a[i]);
printf("\n");
for(int i = 0; i < len; i++)
{
if(a[i] != 0)
{
int temp = a[i];
a[i] = a[index0];
a[index0] = temp;
index0++;
}
}
for(int i = 0; i < len; i++)
printf("%d \t",a[i]);
printf("\n");

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

here is my solution:

#include <iostream>
using namespace std;

main()
{
int input[]={12,4,0,343,2,0,323,0,23};
int index=0;
int size= sizeof(input)/sizeof(int);

for(int i=0;i<size;i++) {
if(input[i] != 0){
if(i-index>0) {
input[index]=input[i];
index++;
}
else index++;
}
}
for(;index<size;index++) input[index]=0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

// a is the array
// n is the size of the array
void f(int* a, int n)
{
if(n<0) return;

int zeroSt = -1; // point to the first 0 element
for(int i=0;i<n;++i)
{
if(a[i]!=0)
{
if(zeroSt != -1)
{
a[zeroSt++]=a[i];
a[i]=0;
}
}
else
{
if(zeroSt == -1)
zeroSt = i;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java version - O(n) time and O(1) space

package arrays;

public class MoveZeroesToEndInplace {
public static void main(String[] args) {
int a[] = { 1, 2, 0, 4, 0, 0, 8,9,0,2,3,0,4,5 };

move_zeroes_to_end(a);
for (int i : a) {
System.out.print(i+" ");
}
}

private static void move_zeroes_to_end(int[] a) {

int index = -1;
int num_zeroes = 0;

// find the first zero
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
index = i;
num_zeroes++;
break;
}
}
if (index != -1) {
int j = index + 1;
while (j < a.length) {
if (a[j] != 0) {
a[index] = a[j];
index++;
j++;
} else if (a[j] == 0) {
j++;
num_zeroes++;
}
}
while(num_zeroes-- > 0){
a[index++]=0;
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
#include <stdio.h>
#include <conio.h>

main()
{

int i=0;
int j= 9;
int k=0;
int arr[10], arr1[10];

printf("Enter numbers for array :");
for(i=0;i<10;i++)
scanf("%d",&arr[i]);

printf(" \n You entered :\n ");
for(i=0;i<10;i++)
printf("arr[%d] = %d",i,arr[i]);

printf("After refinement : \n");
for(i=0;i<10;i++)
{
if(arr[i] == 0)
{
arr1[j]=arr[i];
j--;
}
else
{
arr1[k]=arr[i];
k++;
}

}

for(i=0;i<10;i++)
printf("%d \n",arr1[i]);
getch();

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

# ruby : push zeroes to end of array
p nums = [0, 2, 4, 0, 3, 0, 19, 34, 0, 12, 0, 3]
nums.each_with_index do |num, idx|
if num == 0
nums.delete_at(idx)
nums << 0
end
end
p nums

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>

void pushCharsToEnd(std::string& str, char c)
{
int cCount = 0;
for(auto it = str.begin(); it != str.end(); it++)
{
if(*it == c)
cCount++;
else if(cCount > 0)
{
std::swap(*(it - cCount), *it);
}
}
}

int main(int argc, char** argv)
{
std::string input;
std::getline(std::cin, input);
pushCharsToEnd(input, 'l');
std::cout << std::endl << input;
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

static void push0()
{
int[] arr = {0, 0, 1, 2, 0, 4, 0, 0 ,8 ,9}; //{1,9,9,4,0,0,2,7,0,6,7}; //

int index = 0;

for (int i = 0; i < arr.Length; i++)
{
if (arr[i] != 0)
{
arr[index] = arr[i];
if(index != i) arr[i] = 0;

index++;
}
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.