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.
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++;
}
}
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
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–;
}
}
#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();
}
public static void shiftZeroToEnd(){
int[] a = {3,0, 0 ,4 ,0 ,5, 0, 6, 7, 8, 0, 0, 9};
for (int i = 0; i < a.length-1; i++) {
if(a[i] != 0){
continue;
}
for (int j = i+1; j >”+ a);
}
public static void shiftZeroToEnd(){
int[] a = {3,0, 0 ,4 ,0 ,5, 0, 6, 7, 8, 0, 0, 9};
for (int i = 0; i < a.length-1; i++) {
if(a[i] != 0){
continue;
}
for (int j = i+1; j < a.length; j++) {
if(a[j] != 0){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
break;
}
}
}
}