Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
A minor correction to the above code is to initialize i to (size-1) instead of size in the second for loop above.
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;
}
Python version.
def move_zeros(numbers):
leftIdx = 0
rightIdx = len(numbers)-1
while leftIdx < rightIdx:
if numbers[leftIdx] != 0:
leftIdx += 1
continue
if numbers[rightIdx] != 0:
numbers[leftIdx] = numbers[rightIdx]
numbers[rightIdx] = 0
rightIdx -= 1
continue
rightIdx -= 1
return numbers
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;
}
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
}
}
}
}
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.
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
}
}
}
}
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
}
}
}
}
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++;
}
}
}
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;
}
}
public void Move(int[] a,int pos)
{
int current = pos;
while (a[current] != 0 && current < a.Length)
{
current++;
}
if (current != a.Length-1 && check(a, current))
{
for (int i = current; i < a.Length - 1; i++)
{
swap(ref a[i], ref a[i + 1]);
}
Move(a, current);
}
}
private void swap(ref int a, ref int b)
{
int t = a;
a = b;
b = t;
}
private bool check(int[] a, int current)
{
for (int i = current; i < a.Length; i++)
if (a[i] != 0)
return true;
return false;
}
#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);
}
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;
}
}
}
#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;
}
}
#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;
}
#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);
printf("\nEnter your number:\n");
for(i=0;i<len;i++)
{
scanf("%d",&num[i]);
}
printf("\nYour number:\n");
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;
}
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 :)
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.
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]+" ");
}
}
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]+" ");
}
}
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]+" ");
}
}
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]+" ");
}
}
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.
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..
#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);
}
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();
}
}
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
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";
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";
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;
}
#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();
}
According to question all values should be in ascending order and push the zero to the end...
Find the answer below
#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;
}
#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;
}
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;
}
}
}
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;
}
}
}
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++;
}
}
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;
}
}
}
<?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)));
?>
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;
}
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;
}
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]+" ");
}
}
#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;
}
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]+" ");
}
}
Pseudo code with O(n)
(Lemme know if it's wrong!)
int pos=0;
for (int i=0; i<arr.length; i++)
#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");
}
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;
}
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;
}
}
}
}
{
#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();
}
}
#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;
}
void
zp(int a[], int n)
{
int z = 0;
int nz = 0;
int idx = 0;
int i;
while (1) {
// position z
z = idx;
while (z < n && a[z]) z++;
if (z == n) break;
// position nz after z
nz = z + 1;
while (nz < n && !a[nz]) nz++;
if (nz == n) break;
a[z++] = a[nz];
a[nz++] = 0;
}
printf("\nZero pushed out : ");
for (i=0; i < n; i++) {
printf("%d, ", a[i]);
}
}
//Push all zeros in the matrix to the end
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int i,k ;
cout<<"Enter the number of elements in the array " ;
cin>>i ;
int arr[i] ;
for(int p=0;p<i;p++)
cin>>arr[p] ;
for(int p=0;p<i;p++)
{
if(arr[p]==0)
{
for(int j=p;j<i;j++)
if(arr[j]!=0)
{
k=j ;
int temp=arr[k] ;
arr[k]=arr[p] ;
arr[p]=temp ;
}
}
}
cout<<"Output:"<<endl ;
for(int p=0;p<i;p++)
cout<<arr[p]<<" " ;
getch() ;
return 0 ;
}
public void putNumbersAtEnd(int[] arrayNum)
{
if(arrayNum.length < 2) return;
int pointer1=0;
int pointer2=1;
int temp;
while(pointer2 <arrayNum.length)
{
if(arrayNum[pointer1]==0 && arrayNum[pointer2]!=0)
{
//Swap the values
temp =arrayNum[pointer1];
arrayNum[pointer1] = arrayNum[pointer2];
arrayNum[pointer2] = temp;
}
if(arrayNum[pointer1]!=0)
{
pointer1++;
}
pointer2++;
}
}
package interview_questions;
import java.util.Arrays;
/**
*
* @author just_do_it
*
*/
public class PushZerosToEnd {
static void pushZerosToEnd(int[] a){
int n = a.length;
// swap zero with next non-zero element
// keep track of number of zeroes accumulated
int numZeroesAccumulated = 0;
int numNonZeroesProcessed = 0;
int currentIndex = 0;
while( numZeroesAccumulated + numNonZeroesProcessed < n){
if(a[currentIndex] == 0){
numZeroesAccumulated++;
currentIndex++;
} else {
if(numZeroesAccumulated == 0){
} else {
// swap with a zero
int t = a[currentIndex];
a[currentIndex] = 0; // a[numNonZeroesProcessed]
a[numNonZeroesProcessed] = t;
}
numNonZeroesProcessed++;
currentIndex++;
}
}
}
public static void main(String[] args){
int[] sample = { 1 , 2 , 0 , 4 , 0 , 0 , 8 };
System.out.println(Arrays.toString(sample));
pushZerosToEnd(sample);
System.out.println(Arrays.toString(sample));
}
}
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a[100];
int i,j,k,n;
printf("enter the size of array\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<1;i++)
{
for(j=0;j<n;j++)
{
if(a[j]!=0)
{
a[i]=a[j];
i++;
}
}
break;
}
for(k=i+1;k<n;k++)
{
a[k]=0;
}
for(k=0;k<n;k++)
{
printf("%d",a[k]);
}
return 0;
}
Python, O(n), employs 2 running index: rear, front
def pushZero(A):
rear = 0
front = 0
zeroes = 0
# initization; find the first zero
while front < len(A):
if A[front] == 0:
zeroes += 1
# rear jumps to front where the zero is located
rear = front
front += 1
break
front += 1
# No zero found
if front == (len(A)-1):
return zeroes
# front and rear are at the first found 0
else:
while front < len(A): # front runs til the end of array
if A[front] != 0: #front keeps running and swaping with rear
# swap front to the zero location where rear is at
A[rear] = A[front]
A[front] = 0
# advances
rear += 1
front += 1
else: #A[front] == 0; front just keep running
zeroes += 1
front += 1
return zeroes
if __name__ == '__main__':
A = [1, 0, 2, 0, 0, 3, 4]
z = pushZero(A)
print z, A
include <stdio.h>
#define N 8
int A1[N] = { 0, 0, 0, 0, -1, 2, 3, 4};
int A2[N] = {-1, 2, 3, 4, 0, 0, 0, 0};
int A3[N] = { 0, 0, 0, 0, 0, 0, 0, 0};
int A4[N] = { 0, 0, -1, 2, 3, 4, 0, 0};
int A5[N] = { 0, 0, 0, 0, -1, 2, 3, 4};
int A6[N] = { -1, -2, -3, -4, -5, -6, -7, -9};
int A7[N] = { -1, -2, -3, -4, -5, -6, -7, 0};
int A8[N] = { -1, -2, -3, 0, -5, -6, -7, 0};
int A9[N] = { 0, 0, 0, 0, 0, 0, 0, -1};
int
getNonZeroNum(int *A)
{
int start;
int end;
int cnt;
cnt = 0;
start = 0;
end = N - 1;
while (end >= start) {
if (!A[start]) {
A[start] = A[end];
end--;
cnt++;
} else {
start++;
}
}
return N - cnt;
}
int
main(void)
{
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A1[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A2[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 0 == getNonZeroNum(&A3[0]) ? 0 : -1);
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A4[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A5[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 8 == getNonZeroNum(&A6[0]) ? 8 : -1);
printf("nonzero elemnets %d\n", 7 == getNonZeroNum(&A7[0]) ? 7 : -1);
printf("nonzero elemnets %d\n", 6 == getNonZeroNum(&A8[0]) ? 6 : -1);
printf("nonzero elemnets %d\n", 1 == getNonZeroNum(&A9[0]) ? 1 : -1);
return 0;
}
include <stdio.h>
#define N 8
int A1[N] = { 0, 0, 0, 0, -1, 2, 3, 4};
int A2[N] = {-1, 2, 3, 4, 0, 0, 0, 0};
int A3[N] = { 0, 0, 0, 0, 0, 0, 0, 0};
int A4[N] = { 0, 0, -1, 2, 3, 4, 0, 0};
int A5[N] = { 0, 0, 0, 0, -1, 2, 3, 4};
int A6[N] = { -1, -2, -3, -4, -5, -6, -7, -9};
int A7[N] = { -1, -2, -3, -4, -5, -6, -7, 0};
int A8[N] = { -1, -2, -3, 0, -5, -6, -7, 0};
int A9[N] = { 0, 0, 0, 0, 0, 0, 0, -1};
int
getNonZeroNum(int *A)
{
int start;
int end;
int cnt;
cnt = 0;
start = 0;
end = N - 1;
while (end >= start) {
if (!A[start]) {
A[start] = A[end];
end--;
cnt++;
} else {
start++;
}
}
return N - cnt;
}
int
main(void)
{
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A1[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A2[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 0 == getNonZeroNum(&A3[0]) ? 0 : -1);
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A4[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 4 == getNonZeroNum(&A5[0]) ? 4 : -1);
printf("nonzero elemnets %d\n", 8 == getNonZeroNum(&A6[0]) ? 8 : -1);
printf("nonzero elemnets %d\n", 7 == getNonZeroNum(&A7[0]) ? 7 : -1);
printf("nonzero elemnets %d\n", 6 == getNonZeroNum(&A8[0]) ? 6 : -1);
printf("nonzero elemnets %d\n", 1 == getNonZeroNum(&A9[0]) ? 1 : -1);
return 0;
}
We can make it using only one for loop by keeping the substituteIndex.
Here is the ObjectiveC code
- (NSMutableArray *)moveZerosToEnd:(NSMutableArray *)collection {
int substituteIndex = -1;
for (int itemIndex = 0; itemIndex < collection.count; itemIndex++) {
if ([collection[itemIndex] intValue] == 0) {
if(substituteIndex == -1)
substituteIndex++;
}
else {
collection[substituteIndex] = collection[itemIndex];
collection[itemIndex] = [NSNumber numberWithInt:0];
substituteIndex++;
}
}
return collection;
}
Example:
Input: {0,1, 9, 8, 0, 4, 0, 0, 6, 0}
Output: {1, 9, 8, 4, 6, 0, 0, 0, 0,0}
#import <Foundation/Foundation.h>
#import <stdio.h>
@interface ArrayManipulator : NSObject
- (NSMutableArray *)moveZerosToEnd:(NSMutableArray *)temp;
@end
@implementation ArrayManipulator
- (NSMutableArray *)moveZerosToEnd:(NSMutableArray *)collection {
int substituteIndex = -1;
for (int itemIndex = 0; itemIndex < collection.count; itemIndex++) {
if ([collection[itemIndex] intValue] == 0) {
if(substituteIndex == -1)
substituteIndex++;
}
else {
collection[substituteIndex] = collection[itemIndex];
collection[itemIndex] = [NSNumber numberWithInt:0];
substituteIndex++;
}
}
return collection;
}
@end
int main (int argc, const char * argv[])
{
@autoreleasepool {
//create a collection
NSMutableArray *collection = [[NSMutableArray alloc] initWithObjects:[NSNumber numberWithInt:0],[NSNumber numberWithInt:1],[NSNumber numberWithInt:9],[NSNumber numberWithInt:8],[NSNumber numberWithInt:0],[NSNumber numberWithInt:4],[NSNumber numberWithInt:0],[NSNumber numberWithInt:0],[NSNumber numberWithInt:6],[NSNumber numberWithInt:0], nil];
ArrayManipulator *arrayManipulator = [[ArrayManipulator alloc] init];
collection = [arrayManipulator moveZerosToEnd:collection];
//printing the output
for (int itemIndex = 0; itemIndex < collection.count; itemIndex++) {
printf("%d\n", [collection[itemIndex] intValue]);
}
}
}
#include <iostream>
#include <cstddef>
int x[] = {1,2,0,4,0,0,8};
int main()
{
size_t len = sizeof(x)/sizeof(x[0]);
for (size_t i = 0; i < len; ++i)
{
// found zero
if (0 == x[i])
{
// start searching for non-zero
size_t j = i;
while (0 == x[j] && j < len) j++;
// if we didn't find one, list is sorted
if (j >= len)
break;
// swap. We can just zero out x[j] since we know we're
// looking for zeros and x[i] was originally zero
x[i] = x[j];
x[j] = 0;
}
}
for (auto & i: x) std::cout << i << std::endl;
}
/* output:
1
2
4
8
0
0
0
*/
Python answer:
def move_zeros(numbers):
leftIdx = 0
rightIdx = len(numbers)-1
while leftIdx < rightIdx:
if numbers[leftIdx] != 0:
leftIdx += 1
continue
if numbers[rightIdx] != 0:
numbers[leftIdx] = numbers[rightIdx]
numbers[rightIdx] = 0
rightIdx -= 1
continue
rightIdx -= 1
return numbers
C version O(n):
- renan.cakirerk March 14, 2012