# Shifting zeros to end in an array

Given an array with sorted numbers and zeros in between them, than how could we rearrange the array such that all the zeros are placed at end in O(1) space complexity.

ex: I/p: 3 0 0 4 0 5 0 6 7 8 0 0 9
o/p: 3 4 5 6 7 8 9 0 0 0 0 0 0
Method1 :

```int* shiftZeroToEnd(int *a, int n) // n is size of array
{
int i,firstZero = -1;
for(i=0;i<n;i++) // finding where first zero exists
{
if(a[i]==0)
{
firstZero=i;
break;
}
}
if(firstZero== -1) // no zeros in array
return a;
for(i=firstZero+1;i<n;i++)
{
if(a[i]!=0)
{
swap(a,i,firstZero); //swapping a[i] with a[firstZero]
firstZero++;
}
}
return a;
}
```

Method 2 :

Here is another solution in O(n)

```int * shiftZeroToEnd(int *a,int n)
{
int pos = 0, i, count_zero;

for(i = 0; i <= n-1; i++)
{
if(a[i] != 0) {
a[pos] = a[i];
pos++;
}
}
for(i = n-1; i >= pos; i--)
a[i] = 0;
return a;
}
```

If there is any better way to implement this algorithm, please do comment.

### 4 Thoughts on “Shifting zeros to end in an array”

1. Input Arr[] = {0,1,5,0,0,4,7,0,2}, Size = 9;

int i = 0, j = Size – 1;
while ( i != j ){

if( a[i] == 0 && a[j] == 0 ){
j–;
}
else if( a[i] == 0 && a[j] != 0 ){
Swap( a[i] , a[j] );
i++;
j–;
}
else if( a[i] != 0 && a[j] == 0 ){
i++;
j–;
}
else if( a[i] != 0 && a[j] != 0 ){
i++;
}
}

2. P Karthik on September 13, 2014 at 10:58 am said:

import java.util.Scanner;
import java.lang.*;
/**
*
* @author PKS
*/
public class Endzero {

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in); // TODO code application logic here

System.out.println(“Enter the Array Size: “);

int size = Integer.parseInt(sc.nextLine());

int arr[] = new int[size]; // used to store array element

for(int i=0;i<size;i++)
arr[i] = Integer.parseInt(sc.next());

int k=0; // used to store non zero values starting from zero'th index
// of an array
for(int j=0;j=k) // store zero when j greather then k
arr[j]=0; // after completing loop all zero moved back
}

for(int i=0;i<size;i++)
System.out.print(arr[i]+" ");
}
}

Output:
Enter the Array Size:
5
1 0 2 0 3
1 2 3 0 0

3. Shobhank on October 21, 2014 at 3:55 am said:

int z = a.length-1;
for(int i=0;i<z;i++){
while(a[i] == 0 && a[z] == 0){
z–;
}
if(a[i] == 0){
a[i] = a[z];
a[z] = 0;
z–;
}
}

4. Parminder Kumar Bharti on May 31, 2015 at 12:09 pm said:

#include
#include

void shiftZeorsAtEnd(int Arr[],int size)
{
int j,N;
j=0;
N=size-1;
int newArr[20];

for(int i=0;i<size;++i)
{
if(Arr[i] != 0)
newArr[j++]=Arr[i];
else
newArr[N--]=Arr[i];

}

printf("Output is \n");

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

}

main()
{
int Arr[]={1,0,0,9,1,0,8,0,6,0,25,35,0,0,11};

shiftZeorsAtEnd(Arr,15);
getch();
}