Facebook Interview Question Android test engineers
Country: United States
Interview Type: Phone Interview
In the worst case, you pass an array of 2 times and complexity will be O(2n). O(2n) is the same class complexity as O(n), but exists solution with exact complexity O(n).
O(1*N) time complexity and O(1) space complexity:
def nonzero(array):
zero_count = len(array)-1
for i in range(0,len(array)-1):
if(i+1 >= zero_count):
break
if(array[i] == 0):
while(array[zero_count] == 0):
zero_count -= 1
array[i] = array[zero_count]
array[zero_count] = 0
print(array)
if(array[i] == 0): return i
else: return i+1
The python solution will not work in case of all zeros.
Check this line:
while(array[zero_count] == 0)
def pushZerosToEnd(arr,n):
count = 0;
# Traverse the array. If element encountered is non-zero, then
# replace the element at index 'count' with this element
for i in range(n):
if arr[i] != 0:
count+=1 # here count is incremented
arr[count-1] = arr[i]
print (arr)
noncount=count
## Now all non-zero elements have been shifted to front and 'count' is
# set as index of first 0. Make all elements 0 from count to end.
while (count < n):
count+=1
arr[count-1] = 0
print (arr)
return noncount
Here is my solution
int testArr[7] = {0,1,4,0,0,0,91};
int size =(int)(sizeof(testArr)/sizeof(testArr[0]));
for(int i=0, j=size-1; i<j; )
{
if(testArr[i]==0)
{
if(testArr[j] != 0)
{
testArr[i] = testArr[j];
testArr[j] = 0;
i++; j--;
}
else if(testArr[j] == 0)
j--;
}
else
i++;
}
void func2(int arr[], int size)
{
int i = 0;
int j = 1;
while(i < size-1 && j < size)
{
if(arr[i] == 0)
{
while(arr[j] == 0 && j<size) j++;
if(j < size)
{
arr[i] = arr[j];
arr[j] = 0;
}
}
i++;
}
}
var noZeroAry = (function(intAry) {
var sortAry = function(intAry) {
var start = 0;
var end = intAry.length - 1;
for (start = 0; start < end; start++) {
if (intAry[start] === 0) {
while (end > 0 && intAry[end] === 0) {
end--;
}
intAry[start] = intAry[end];
intAry[end] = 0;
end--;
}
}
};
return function(intAry) {
sortAry(intAry);
return intAry;
}
})();
console.log(noZeroAry([1, 1, 1]));
O(n) time, O(1) space, super simple. Written in Python, has a unittest.
def move_nonzero_to_left(lst):
nonzero_count = 0
for index, value in enumerate(lst):
if value:
if index != nonzero_count:
lst[nonzero_count], lst[index] = value, 0
nonzero_count += 1
return nonzero_count, lst
# Test checking that it works
import unittest
class TestCase(unittest.TestCase):
def test_move_nonzero_to_left(self):
counter, lst = move_nonzero_to_left([ 1, 0, 2, 0, 0, 3, 4 ])
self.assertEqual(counter, 4)
self.assertEqual(lst, [1, 2, 3, 4, 0, 0, 0] )
unittest.main()
have two pointers. one that always points to zero and other looking for non zero element.
track the count of swaps. If zero pointer is not pointing to zero element, increment count and move ahead.
Space : O(1)
Time : O(n)
package com.project.euler;
public class NoZero {
public static void main(String[] arg){
int[] arr = {0,0,-1,1,0,2,3,0,0,5};//{1,0,2,0,0,3,4};
int count = 0;
for(int i=1,j=0;i<arr.length;i++){
if(arr[j]!=0){
j++;
count++;
if(i==arr.length-1 && arr[i]!=0)
count++;
}else{
if(arr[i]!=0){
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
j++;
count++;
}
}
}
System.out.print("Updated array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
System.out.println("No. of non Zero elements : "+count);
}
}
This solution is similar to quicksort algorithm in part of partition of array, but simplier. Complexity is O(n).
public static int BringNzeToLeft(int[] arr)
{
int i = 0;
int j = arr.Length - 1;
while (true)
{
while (i < arr.Length && arr[i] != 0)
i++;
while (j >= 0 && arr[j] == 0)
j--;
if (i < j)
Swap(arr, i, j);
else
return i;
i++;
j--;
}
}
private static void Swap(int[] arr, int left, int right)
{
var tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
Move from both end and do swap in one pass.
static void SwapZeros(int[] input)
{
if (input == null || input.Length <= 1)
return;
int left = 0;
int right = input.Length - 1;
while (left < right)
{
// first get to first zero from left
while (input[left] != 0 && left < input.Length)
left++;
// get to first nonzero from right
while (input[right] == 0 && right >0)
right--;
if (left < right)
{
// swap
input[left] = input[right];
input[right] = 0;
// move left & right
left++;
right--;
}
}
}
Two pointers, one from the beginning points to nonzero element, the other one is from the end points to nonzero element. We should switch these values.
public class MoveNonzeroLeft {
public static int findNextNonZeroIndex(int[] array, int index){
int nonZeroIndex = 0;
for(int i = index -1; i>0; i--){
if(array[i] != 0){
nonZeroIndex = i;
break;
}
}
return nonZeroIndex;
}
public static int findNextZeroIndex(int[] array, int index){
int zeroIndex = 0;
for(int i = index + 1; i< array.length;i++){
if(array[i] == 0){
zeroIndex = i;
break;
}
}
return zeroIndex;
}
public static void moveNonzeroLeft(int[] array){
int zeroIndex = 0;
int nonZeroIndex = 0;
zeroIndex = findNextZeroIndex(array, 0);
nonZeroIndex = findNextNonZeroIndex(array, array.length);
while(true){
if(zeroIndex < nonZeroIndex){
/*
* swap
*/
int temp = array[nonZeroIndex];
array[nonZeroIndex] = 0;
array[zeroIndex] = temp;
zeroIndex = findNextZeroIndex(array, zeroIndex);
nonZeroIndex = findNextNonZeroIndex(array, nonZeroIndex);
}else{
break;
}
}
}
public static void main(String[] args) {
int[] array = {1, 0, 2, 0, 0, 3, 4};
MoveNonzeroLeft.moveNonzeroLeft(array);
for(int i = 0 ;i < array.length ; i++){
System.out.print(array[i]+" ");
}
}
}
int[] iarray = {1, 0, 2, 0, 0, 3, 4};
int count = 0;
for(int i = 0 ; i < iarray.length-count; i++){
if(iarray[i] == 0) {
count++;
iarray[i] = iarray[iarray.length-count];
iarray[iarray.length-count] = 0;
i=-1;
}
}
System.out.print("Elements : ");
for(int j = 0 ;j<iarray.length;j++)
System.out.print(iarray[j]+" ");
System.out.println();
System.out.println("Count: "+ count);
#include<stdio.h>
#include<conio.h>
void main()
{
int a[10],i=0,j=0,c,temp;
printf("\nEnter the length\n");
scanf_s("%d", &c);
printf("Enter the no in array");
for (int i = 0; i < c; i++)
{
scanf_s("%d",&a[i]) ;
}
j = c-1;
while (i < j)
{
if (a[i] != 0)
{
i++;
continue;
}
if (a[j] == 0)
{
j--;
continue;
}
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
for (int i = 0; i < c; i++)
{
printf("%d\n",a[i]);
}
_getch();
}
#include<stdio.h>
#include<conio.h>
void main()
{
int a[10],i=0,j=0,c,temp;
printf("\nEnter the length\n");
scanf_s("%d", &c);
printf("Enter the no in array");
for (int i = 0; i < c; i++)
{
scanf_s("%d",&a[i]) ;
}
j = c-1;
while (i < j)
{
if (a[i] != 0)
{
i++;
continue;
}
if (a[j] == 0)
{
j--;
continue;
}
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
for (int i = 0; i < c; i++)
{
printf("%d\n",a[i]);
}
_getch();
}
1. Maintain a variable s_z -> It will always be starting(1st) index of zero. Initialize it to -1. s_z = -1;
2. Iterate through an array.
A. While traversing the array, set s_z = i, if we find zero number in the array and initial value of s_z = -1.
B. Else, if it is non-zero element and s_z has updated with 1st index of zero element, swap the element with s_z.
C. After swapping, increment s_z. PS: The next element of current s_z will always be zero.
For instance, if A = [ 1, 0, 6, 0, 0, 3, 4 ];
s_z = 1;
swap A[s_z], A[i] where, i = 2 [index of array]
After swap, new array A = [1,0,0,6,0,3,4]. Right now, s_z = 1. Increment it by 1. new s_z = 2.
and A[s_z] = 2. [Because, you have swapped non-zero with zero element.]
Second instance, A = [ 1, 0, 0, 0, 0, 3, 4 ].
s_z = 1, and i = 5. After Swap, A = [ 1, 3, 0, 0, 0, 0, 4 ]. increment s_z. s_z = 2.
A[s_z] = 0.
{
int[] a = { 1, 0, 2, 0, 0, 3, 4 }; // 1,0,0,0,2,3,0,0
int s_z = -1;
for ( int i = 0; i < a.length; i++ ) {
if ( a[i] == 0 && s_z == -1 ) {
s_z = i;
} else if ( a[i] != 0 && s_z != -1 ) {
swap( a, i, s_z );
s_z++;
}
}
}
var swap = function(i,j,array) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
return array;
};
var findNonZeroes = function(array) {
var left = 0
var right = array.length - 1;
var counter = 0;
while (left < right) {
while (left < right && array[left] !== 0) {
left++;
counter++;
}
while (left < right && array[right] === 0) {
right--;
}
if (left < right) {
swap(left,right,array);
counter++;
left++;
right--;
}
}
return counter;
};
public static int[] organizeArr(int[] inputArr) {
int temp;
int left=0;
int right=inputArr.length-1;
if(left==right && inputArr[left]==0) {
System.out.println("number of non zero:"+0);
return inputArr;
}
while(true){
if(inputArr[left]==0 && inputArr[right]!=0){
temp=inputArr[left];
inputArr[left]=inputArr[right];
inputArr[right]=temp;
}
left++;
while(true){
if(inputArr[right]==0)
right--;
else
break;
}
if(left>right)
{
System.out.println("number of non zero:"+left);
break;
}
}
return inputArr;
}
Below is my rendition for the solution. I had some fun and timed the full the operation, but it is not needed, obviously.
#include <stdio.h>
#include <ctype.h>
#include <time.h>
void printArray( int array[], int size );
void printCount( int array[], int arr_size);
void sortArray( int array[], int arr_size);
int main()
{
clock_t t1, t2; //Benchmarking purposes, just for fun
t1 = clock();
int arr[] = {1, 0, 2, 0, 0, 3, 4};
int i, temp;
int arr_size = sizeof(arr)/sizeof(arr[0]); //storing array size, i.e., 7
int j = arr_size-1; //accounting for indexing --> 0 through 6 instead of 1 through 7
for( i = 0; i < arr_size; i++ ) //iterating through each element in the array
{
if ( i < j ) //checking to see if lower and index aren't overlapping
{
/*does lower index's value equal 0 and does higher index's value not equal 0 */
if( arr[i] == 0 && arr[j] != 0 )
{
/* swapping two elements */
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j--;
}
/*does lower index's value equal 0 and does higher index's value equal 0 */
else if ( arr[i] == 0 && arr[j] == 0 )
{
temp = arr[i];
arr[i] = arr[j - 1];
arr[j-1] = temp;
i--;
j--;
}
/* ~ after first iteration --> 1 0 2 0 0 3 4
~ after second iteration --> 1 4 2 0 0 3 0
~ after third iteration --> 1 4 2 0 0 3 0
~ after fourth iteration --> 1 4 2 3 0 0 0
-- all non zero elements to the left! -- */
}
}
printf("Given Array: \n");
printArray(arr, arr_size); // prints given array to screen --> see function below
sortArray(arr, arr_size); // sorts given array --> see function below
printf("\n");
printCount(arr, arr_size); // prints various stats about array --> see function below
//benchmarking
t2 = clock();
printf("Elapsed Time of Full Operation: %d clocks per second \n\n", (int)(t2-t1));
return 0;
}
void printArray( int array[], int size ) // takes arguments from call above
{
int i;
for( i = 0; i < size; i++ ) // iterates through each index in the array
{
printf("%d ", array[i]); //prints each value of each index to screen
}
printf("\n");
}
void printCount( int array[], int arr_size)
{
int i, count = 0;
for( i = 0; i < arr_size; i++ ) // iterates through each index in the array
{
if( array[i] != 0 ) // checks to see if nonzero element
{
count++; // counts the nonzero elements
}
}
printf("Total Number of Elements in Array: %d\n", arr_size);
printf("\tBreakdown: \n");
printf("\t -Number of Nonzero Elements: %d\n", count);
printf("\t -Number of Zeros: %d\n\n", arr_size - count);
}
void sortArray( int array[], int arr_size )
{
int i, temp;
int j = arr_size-1;
reprocess: // <---------------------------------=
for( i = 0; i < j; i++ )
{
if( array[i] > array[i+1] ) // checks to see if 1st element is bigger than next
{
/* swap */
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
goto reprocess; // goes to reprocess -=
}
}
printf("\nSorted Array:\n");
printArray(array, arr_size); // calls function to print sorted array to screen
}
Following code is discussed here : questiondiscussion.com/questions/547/write-an-algorithm-that-brings-all-nonzero-elements-to-the-left-of-the-array-and-returns-the-number-of-nonzero-elements
#include <stdio.h>
#define MAX 7
int main(void)
{
int arr[7]={0, 6, 1, 8, 0, 0, 9};
int i=0,k=0,temp=0;
for(i=0;i<MAX-1;i++)
{
if(arr[i]==0 ) //if value is zero
{
k=i+1;
while(k<MAX-1 && arr[k]==0 )
//then check which value to its RHS is non zero
{
// k<MAX-1 so that k does not cross its array bound
k++;
}
temp=arr[i];
//then swap zero and nonzero in place
arr[i]=arr[k];
arr[k]=temp;
}
}
for(i=0;i<MAX;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
Here is the code. It also maintains the order of non-zero elements
void change(int arr[],int n)
{
int first=0,count=0;
for(int i=0;i<n;i++)
{
if(arr[i]!=0)
{
arr[first++]=arr[i];
count++;
}
}
for(int i=first;i<n;i++)
{
arr[i]=0;
}
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
printf("\nNo of non zero elements are %d ",count);
}
int main()
{
int arr[]={1,0,2,0,0,3,4};
int n=sizeof(arr)/sizeof(arr[0]);
change(arr,n);
}
public void order(List<Integer> list) {
int count =0;
int size = list.size();
for(int i=0;i<list.size();i++) {
if(list.get(i).intValue() ==0) {
count++;
list.remove(i);
i--;
}
}
for(int i=0 ;i< count; i++) {
list.add(0);
}
System.out.println("number of non-zero numbers "+(size-count));
}
public void display(List<Integer> list) {
for(Integer element : list) {
System.out.println(element);
}
}
public void order(List<Integer> list) {
int count =0;
int size = list.size();
for(int i=0;i<list.size();i++) {
if(list.get(i).intValue() ==0) {
count++;
list.remove(i);
i--;
}
}
for(int i=0 ;i< count; i++) {
list.add(0);
}
System.out.println("number of non-zero numbers "+(size-count));
}
public void display(List<Integer> list) {
for(Integer element : list) {
System.out.println(element);
}
}
I tried with simple two for loops and a boolean flag.
public static int[] moveZerosToRight(int[] array) {
int length = array.length;
for (int i = 0 ; i < length ; i++) {
int current = array[i];
if(current == 0) {
boolean flag = true;
for(int j = length - 1; j > i && flag == true ; j--){
if(array[j] != 0) {
int temp = current ;
array[i] = array[j];
array[j] = temp;
flag = false;
}
}
}
}
return array;
}
checked with negative values as well.
Almost everyone is over-complicating this problem.
public class Main {
public static void main(String [] args) {
int[] theArray = {1, 0, 2, 0, 0, 3, 4};
int latestIndex = 0;
for (int i = 0; i < theArray.length; i++)
{
if (theArray[i] != 0)
{
int temp = theArray[i];
theArray[i] = theArray[latestIndex];
theArray[latestIndex] = temp;
latestIndex++;
}
}
System.out.println(latestIndex);
}
}
Java approach for this. I did it to move all zeros to the right and to the left ;) :
public static void main(String [] args){
int arr[] = {0, 0, 1, 0, 1, 3, 0, 4, 0, 0, 5};
transformArrayToRight(arr);
for(Integer i : arr)
System.out.print(i + " ");
System.out.println("");
}
private static void transformArrayToLeft(int[] arr) {
Deque d = new LinkedList();
for(int i = 0; i < arr.length; i++){
if(arr[i] != 0)
d.addLast(arr[i]);
arr[i] = 0;
}
int i = 0;
while(!d.isEmpty()){
arr[i] = (int) d.getFirst();
d.removeFirst();
i++;
}
}
private static void transformArrayToRight(int[] arr) {
Deque d = new LinkedList();
for(int i = 0; i < arr.length; i++){
if(arr[i] != 0)
d.addLast(arr[i]);
arr[i] = 0;
}
int i = arr.length - 1;
while(!d.isEmpty()){
arr[i] = (int) d.getLast();
d.removeLast();
i--;
}
}
public static void main(String[] args) {
//int[] a ={1,0,8,0,0,-1,0};
int[] a ={0,0,2,3,2,4,0,0,0};
//int[] a ={1,3,2,3,5,0,0,0,1,1,1,0};
//int[] a ={1,0,2,1};
//int[] a ={1,2,3,4,5,6,0,0,7,0,0,0};
int nonZero=0;
int zero = a.length-1;
int temp;
System.out.println("Before sort\n");
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
int count =0;
for(int i=0;i<a.length;i++){
//System.out.print(a[i]+" ");
if(i< zero){
if(a[i] == 0){
temp = a[zero];
while(i<zero){
if(temp != 0){
count++;
a[zero]= a[i];
a[i]= temp;
break;
}
zero--;
temp = a[zero];
}
}else{
count++;
}
}else{
break;
}
}
System.out.println("\nAfter sort\n");
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println("\nNon Zero Count:"+count);
}
static void Main(string[] args)
{
int[] input = new int[]
{
1, 0, 2, 0, 0, 3, 4
};
int result = Process(input);
}
private static int Process(IList<int> input)
{
int numberOfNonZeroNumbers = 0;
for (int processingIndex = 0; processingIndex < input.Count; processingIndex++)
{
if (input[processingIndex] == 0) continue;
Swap(input, processingIndex, numberOfNonZeroNumbers);
numberOfNonZeroNumbers++;
}
return numberOfNonZeroNumbers;
}
private static void Swap(IList<int> inputArray, int firstIndex, int secondIndex)
{
int tempNumberHolder = inputArray[firstIndex];
inputArray[firstIndex] = inputArray[secondIndex];
inputArray[secondIndex] = tempNumberHolder;
}
I prefer readable to terse lol
I am not sure if my solution is good or not. But I only create another array with all 0. Then I scan the given array, once I reach a not-zero element, I put it in the new array. It is O(n). But it needs an extra array.
import java.util.Arrays;
class numshift
{
private int[] array;
public numshift(int[] a)
{
array = a;
}
public void swap(int[] a, int i, int j)
{
int b = a[i];
a[i] = a[j];
a[j] = b;
}
public int[] shift()
{
int[] result = new int[array.length];
Arrays.fill(result, 0);
int index = 0;
for(int i=0; i<array.length; i++)
{
if(array[i] != 0)
{
result[index] = array[i];
index++;
}
}
return result;
}
}
public class Main {
public static void main(String args[])
{
int[] a = {1,0,2,0,0,3,4};
numshift n = new numshift(a);
a = n.shift();
for(int i=0; i<a.length; i++)
{
System.out.print(a[i]);
System.out.print(" ");
}
System.out.println();
}
}
public class TestProgram {
static final int[] INPUT_ARRAY = { 1, 0, 2, 0, 0, 3, 4 };
public static void main(String[] args) {
int endIndex = INPUT_ARRAY.length - 1;
for (int i = 0; i <= endIndex; i++) {
if (INPUT_ARRAY[i] == 0 && INPUT_ARRAY[endIndex] == 0) {
i++;
endIndex--;
continue;
}
if (INPUT_ARRAY[i] == 0) {
while (true) {
if (INPUT_ARRAY[endIndex] != 0) {
break;
} else {
endIndex--;
}
}
int temp = INPUT_ARRAY[i];
INPUT_ARRAY[i] = INPUT_ARRAY[endIndex];
INPUT_ARRAY[endIndex] = temp;
endIndex--;
}
}
System.out.print("[ ");
for (int i = 0; i < INPUT_ARRAY.length; i++)
System.out.print(INPUT_ARRAY[i] + " ");
System.out.print("]");
}
}
Have two iterators, one positioned at the start,i, the other positioned at the end of the array, j.
Increment i and check if the element is zero. If the element is zero swap with element in position j and increment the counter. Decrease iterator j and continue until i==j.
The answer is obtained by subtracting the counter from the length of the array.
#include<iostream>
#include<string>
using namespace std;
int nonZeroCount(int a[], int length)
{
if(length == 1)
{
if(a[0] == 0)
return 0;
else
return 1;
}
int i = 0;
int j = length -1;
int count = 0;
while(i != j)
{
if(a[i] == 0)
{
//swap element a[i] with element at end of array, a[j]
int temp = a[i];
a[i] = a[j];
a[j] = temp;
j--;
count++;
}
else
{
i++;
}
}
if(a[i] == 0 )
{
count++;
}
return length - count;
}
int main()
{
int a[] = { 1, 0, 2, 0, 0, 3, 4 };
cout << "Answer = " << nonZeroCount(a, 7) << endl;
}
Working code in O(n)
private int[] moveZeros(int[] array) {
int startIndex = 0;
int endIndex = 1;
for (int i = 0; i < array.length-1; i++) {
if( array[startIndex]==0&&array[endIndex]!=0){
array[startIndex] = array[endIndex];
array[endIndex] = 0;
startIndex++;
endIndex++;
}else if(array[startIndex]!=0&&array[endIndex]==0){
startIndex++;
endIndex++;
}else if(array[startIndex]==0&&array[endIndex]==0){
endIndex++;
}
}
return array;
}
PHP variant, there is no need to swap zeros, so we can cheat here a little =)
function getNoneZerosNum($array)
{
if (empty($array) || !is_array($array)) {
return false;
}
$num = sizeof($array);
$lastNoneZeroIndex = 0;
for ($i = 0; $i < $num; $i++) {
if ($array[$i] != 0) {
$array[$lastNoneZeroIndex] = $array[$i];
if ($i != 0) {
$array[$i] = 0;
}
$lastNoneZeroIndex++;
continue;
}
}
return $lastNoneZeroIndex;
}
#include<stdio.h>
int array[] = {1,0,2,0,0,3,4};
#define SIZEOF_ARRAY sizeof(array)/sizeof(array[0])
int main(int argc, char **argv) {
int i,j,count = SIZEOF_ARRAY;
i = 0; j = count - 1;
while (i <= j) {
if (!array[i]) {
while (!array[j])
j--;
if (i < j) {
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
}
i++;
}
for (i = 0; i < count; ++i)
printf("%d\t",array[i]);
}
#include<stdio.h>
int array[] = {1,0,2,0,0,3,4};
#define SIZEOF_ARRAY sizeof(array)/sizeof(array[0])
int main(int argc, char **argv) {
int i,j,count = SIZEOF_ARRAY;
i = 0; j = count - 1;
while (i <= j) {
if (!array[i]) {
while (!array[j])
j--;
if (i < j) {
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
}
i++;
}
for (i = 0; i < count; ++i)
printf("%d\t",array[i]);
}
#include<stdio.h>
int array[] = {1,0,2,0,0,3,4};
#define SIZEOF_ARRAY sizeof(array)/sizeof(array[0])
int main(int argc, char **argv) {
int i,j,count = SIZEOF_ARRAY;
i = 0; j = count - 1;
while (i++ <= j) {
if (!array[i]) {
while (!array[j])
j--;
if (i < j) {
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
}
}
for (i = 0; i < count; ++i)
printf("%d\t",array[i]);
}
public static int moveZerosRight(int[] a) {
if (a == null || a.length == 0) return 0;
int i = 0;
int j = a.length;
while (i < j) {
if (a[j] == 0) {
j--;
} else if (a[i] != 0) { //&& a[j]!=0
i++;
} else { // a[i] == 0 && a[j]!=0
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
return i;
}
obj c example. O(n) time, O1 space
#import <Foundation/Foundation.h>
int main(int argc, const char * argv[])
{
@autoreleasepool {
NSMutableArray *testArray = [NSMutableArray arrayWithObjects:@0, @3, @5, @0, @0, @0, @1, @3, @1, @3, @5, @0, @0, @1, @0, nil];
long j = testArray.count -1;
for (long i = 0; i <= j; i++) {
if ([testArray[i] integerValue] == 0) {
for (;j >= i; j--) {
if ([testArray[j] integerValue] != 0) {
[testArray exchangeObjectAtIndex:i withObjectAtIndex:j];
j--;
break;
}
}
}
}
// insert code here...
NSLog(@"array us %@ swaps num ara %lu" , testArray, testArray.count - j-1 );
}
return 0;
}
Solution in Java. . Time (n) . Space(1)
{{
public static void shiftZero(int[] tmp){
int i = 0;
int j = tmp.length-1;
while(i < j)
{
if(tmp[i] == 0 && tmp[j] != 0){
tmp[i] = tmp[j];
tmp[j] = 0;
}
while(tmp[i] != 0)
{
i++;
}
while(tmp[j] == 0){
j--;
}
}
System.out.println(Arrays.toString(tmp));
}
}}}
What is the complexity of the following python code? It breaks out early after seeing a number of zeroes.
#!/usr/bin/python
int_array = [1, 0, 2, 0, 0, 3, 4]
zeroes = 0
print("The original array=%s" % str(int_array))
for i in range(0,len(int_array)):
if int_array[i] == 0:
read_idx = i + zeroes
while read_idx < len(int_array) and int_array[read_idx] == 0:
zeroes += 1
read_idx += 1
if read_idx < len(int_array):
print("swapping read_idx=%d to i=%d" % (read_idx,i))
int_array[i] = int_array[read_idx]
int_array[read_idx] = 0
print("i=%2d nz=%2d array=%s" % (i,zeroes,str(int_array)))
# We can break out of here early when we know the rest is 0s.
if zeroes + i + 1 >= len(int_array):
print("All done at i=%d." % i)
break
non_zeroes = len(int_array) - zeroes
print("There were %d non zeroes found." % non_zeroes)
Here is the output:
The original array=[1, 0, 2, 0, 0, 3, 4]
i= 0 nz= 0 array=[1, 0, 2, 0, 0, 3, 4]
swapping read_idx=2 to i=1
i= 1 nz= 1 array=[1, 2, 0, 0, 0, 3, 4]
swapping read_idx=5 to i=2
i= 2 nz= 3 array=[1, 2, 3, 0, 0, 0, 4]
swapping read_idx=6 to i=3
i= 3 nz= 3 array=[1, 2, 3, 4, 0, 0, 0]
All done at i=3.
There were 4 non zeroes found.
My algo:
1.keep two indexes i=0 and j=n-1;
2.if a[i]=0 and a[j]=0 then j--
3.if a[i]!=0 and a[j]=0 then i++ j--
4.if a[i]=0 and a[j]!=0 swap a[i] and a[j] i++ j--
5. if a[i]!=0 and a[j]!=0 then i++
Here is my code
int main()
{
int n;
int i,a[100],j;
cin>>n;
for(i=0;i<n;i++){cin>>a[i];}
i=0,j=n-1;
while(i<=j && i<n && j>=0)
{
if(a[i]==0 && a[j]!=0)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
i++;j--;continue;
}
if(a[i]!=0 && a[j]!=0)
{
i++;
}
if(a[i]!=0 && a[j]==0)
{
i++;j--;continue;
}
if(a[i]==0 && a[j]==0)
{
j--;
}
}
for(i=0;i<n;i++){cout<<a[i]<<" ";}
return 0;
}
<?php
function find(array $numbers, $len, $from, $isZero, $incremental) {
$pos = $from;
while ($pos >= 0 && $pos < $len && ($numbers[$pos] == 0) != $isZero) {
$pos += $incremental;
}
return $pos;
}
function swap(array &$numbers, $a, $b) {
$num = $numbers[$a];
$numbers[$a] = $numbers[$b];
$numbers[$b] = $num;
}
function reorder(array &$numbers) {
$len = count($numbers);
$zero = find($numbers, $len, 0, true, 1);
$nonzero = find($numbers, $len, $len - 1, false, -1);
while ($nonzero >= $zero) {
swap($numbers, $zero, $nonzero);
$zero = find($numbers, $len, $zero, true, 1);
$nonzero = find($numbers, $len, $nonzero, false, -1);
}
}
$numbers = [1, 0, 2, 0, 0, 3, 4];
reorder($numbers);
var_dump($numbers);
public static int[] moveNonZeroLeft(int[] a) {
if (a == null || a.length == 1) {
return a;
}
int j = a.length - 1;
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
while (j > i) {
if (a[j] != 0) {
swap(a, i, j);
j--;
break;
}
j--;
}
}
}
return a;
}
private static void swap(int[] a, int i, int j) {
int k = a[i];
a[i] = a[j];
a[j] = k;
}
Time O(n), space O(1). The partition step of quick sort, with 0 be the pivot.
An index of zero elements from the beginning and an index of non-zero elements from the end. Move the indices closer until they meet or overlap. Swap elements as needed.
public class NonZero {
public static void main(String[] args) {
int[] array = new int[]{1, 0, 2, 0, 0, 3, 4};
processNonZeros(array);
int nze = 0;
System.out.print("[");
for (int k=0; k<array.length; k++) {
System.out.print(array[k]);
if (k<array.length-1) {
System.out.print(", ");
}
if (array[k] != 0) {
nze++;
}
}
System.out.print("] ");
System.out.println(nze);
}
private static void processNonZeros(int[] input) {
int q = 0;
for (int k=0; k<input.length;k++) {
int current = input[q];
if (current != 0) {
q++;
} else {
if (input[k] != 0) {
input[q] = input[k];
input[k] = 0;
q++;
}
}
}
}
}
public static void main(String[] args){
int[] a={1,2,0,0,0,3,0,6,7,4,0,3,7,0};
solve(a);
}
static void solve(int[] a){
int tmp=0;
int tmp2=0;
for(int i=0;i<a.length;i++){
tmp=a[i];
if(tmp==0){
for(int j=i+1;j<a.length;j++){
if(a[j]!=0){
tmp2=a[j];
a[j]=tmp;
a[i]=tmp2;
}
}
}
}
for(int i:a){
System.out.print(i+", ");
}
}
Move and count in single loop, O(n):
int list[28] = {1,0,2,0,0,3,4,9,0,8,7,0,0,7,6,0,5,0,0,0,0,6,6,6,6,6,6,6};
int size = sizeof(list)/sizeof(int);
int counter=0;
int *ptrStart = &list[0];
int *ptrEnd = &list[size-1];
while (ptrStart != ptrEnd){
if(*ptrStart==0){
int temp = *ptrStart;
*ptrStart=*ptrEnd;
*ptrEnd=temp;
ptrStart++;
ptrEnd--;
counter++;
}else{
ptrStart++;
counter++;
if(*ptrEnd==0)
ptrEnd--;
}
}
printf("%d", counter);
I think of this problem a little bit like the partitioning problem in quick sort.
We can think of there being a wall in the place that is our first zero.
1,0,2,0,0,3,4
In general the steps will be.
Find the first zero, lets call this the wall.
Now iterate all indexes after the current wall position such that the value is a non zero value.
If we find a non zero , then lets swap the current wall value which is a zero with the new value, and lets increment our wall position.
Keep going until the currentIndex < length.
Lets see if I can visualize this:
1,0,2,0,0,3,0,4
So our first zero is the #1 index
1,0|,2,0,0,3,0,4
swap our first non zero value with the wall
1,2|0,0,0,3,0,4
increment the wall
1,2,0|,0,0,3,0,4
Then rinse and repeat
void partitionArray(int [] array)
{
int currentIndex = 0;
int currentWall = 0;
//Find first non zero value
for(int i = 0; i<array.length; i++)
{
if(array[i] == 0)
{
currentWall = i;
break;
}
}
currentIndex = currentWall + 1;
while(currentIndex < array.length)
{
if(array[currentIndex] != 0)
{
//swap this item with the wall
int temp = array[currentIndex];
array[currentIndex] = array[currentWall];
array[currentWall] = temp;
//move the wall
currentWall++;
}
currentIndex++;
}
}
I think of this problem a little bit like the partitioning problem in quick sort.
We can think of there being a wall in the place that is our first zero.
1,0,2,0,0,3,4
In general the steps will be.
Find the first zero, lets call this the wall.
Now iterate all indexes after the current wall position such that the value is a non zero value.
If we find a non zero , then lets swap the current wall value which is a zero with the new value, and lets increment our wall position.
Keep going until the currentIndex < length.
Lets see if I can visualize this:
1,0,2,0,0,3,0,4
So our first zero is the #1 index
1,0|,2,0,0,3,0,4
swap our first non zero value with the wall
1,2|0,0,0,3,0,4
increment the wall
1,2,0|,0,0,3,0,4
Then rinse and repeat
void partitionArray(int [] array)
{
int currentIndex = 0;
int currentWall = 0;
//Find first non zero value
for(int i = 0; i<array.length; i++)
{
if(array[i] == 0)
{
currentWall = i;
break;
}
}
currentIndex = currentWall + 1;
while(currentIndex < array.length)
{
if(array[currentIndex] != 0)
{
//swap this item with the wall
int temp = array[currentIndex];
array[currentIndex] = array[currentWall];
array[currentWall] = temp;
//move the wall
currentWall++;
}
currentIndex++;
}
}
private int[] ArrangeNumbersToLeft(int [] input)
{
int lastIndex = input.Length - 1;
for(int i =0;i< input.Length;i++)
{
if (i >= lastIndex)
return input;
if(input[i] == 0)
{
while(input[lastIndex] == 0)
{
lastIndex--;
}
if (lastIndex < i)
return input;
int t = input[i];
input[i] = input[lastIndex];
input[lastIndex] = t;
}
}
return input;
}
private int[] ArrangeNumbersToLeft(int [] input)
{
int lastIndex = input.Length - 1;
for(int i =0;i< input.Length;i++)
{
if (i >= lastIndex)
return input;
if(input[i] == 0)
{
while(input[lastIndex] == 0)
{
lastIndex--;
}
if (lastIndex < i)
return input;
int t = input[i];
input[i] = input[lastIndex];
input[lastIndex] = t;
}
}
return input;
}
private int[] ArrangeNumbersToLeft(int [] input)
{
int lastIndex = input.Length - 1;
for(int i =0;i< input.Length;i++)
{
if (i >= lastIndex)
return input;
if(input[i] == 0)
{
while(input[lastIndex] == 0)
{
lastIndex--;
}
if (lastIndex < i)
return input;
int t = input[i];
input[i] = input[lastIndex];
input[lastIndex] = t;
}
}
return input;
}
private int[] ArrangeNumbersToLeft(int [] input)
{
int lastIndex = input.Length - 1;
for(int i =0;i< input.Length;i++)
{
if (i >= lastIndex)
return input;
if(input[i] == 0)
{
while(input[lastIndex] == 0)
{
lastIndex--;
}
if (lastIndex < i)
return input;
int t = input[i];
input[i] = input[lastIndex];
input[lastIndex] = t;
}
}
return input;
}
/*
Input : [ 1, 0, 2, 0, 0, 3, 4 ]
Output : [ 1, 2, 3, 4, 0, 0, 0 ]
*/
function solve(arr) {
var left = 0;
var right = arr.length - 1;
var length = right;
while (left < right) {
if (arr[left] === 0 && arr[right] !== 0) {
arr[left] = arr[right];
arr[right] = 0;
}
while (arr[left] !== 0 && left < right) {
left++;
}
while (arr[right] === 0 && right > left) {
right--;
}
}
}
static void inPlaceSwap(int[] arr){
int p=0;
int i=1;
while(i < arr.length){
if(arr[p] < arr[i]){
swap(arr, p,i);
p++;
i++;
}
else if (arr[p]==0 && arr[i]==0){
i++;
}
else{
p++;
i++;
}
}
System.out.println(p);
System.out.println(Arrays.toString(arr));
}
Java approach:
public static void main(String[] args) {
int arr[] = {1, 0, 2, 0, 0, 3, 4};
System.out.println(swapNonZeros(arr));
for(int i : arr)
System.out.print(i + " ");
System.out.println();
}
private static int swapNonZeros(int[] arr) {
int zero_index = 0;
for(int i = 0; i < arr.length; i++){
while(arr[i] != 0)
i++;
zero_index = i;
i++;
while(arr[i] == 0){
i++;
if(i == arr.length)
return arr.length - zero_index;
}
swap(arr, i, zero_index);
i = zero_index;
}
return arr.length - zero_index;
}
private static void swap(int[] arr, int i, int zero_index) {
int aux = arr[i];
arr[i] = arr[zero_index];
arr[zero_index] = aux;
}
Output:
3
1 2 3 4 0 0 0
- (void)removeZeroAndDescendTheNonZerFromArray:(NSArray *)iArray {
NSMutableArray *tempArray = [iArray mutableCopy];
[tempArray removeObjectIdenticalTo:@0];
NSSortDescriptor *descendSort = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:NO selector:@selector(compare:)];
[tempArray sortUsingDescriptors:[NSArray arrayWithObject:descendSort]];
NSLog(@"Array Sorted descending order..%@", tempArray);
NSLog(@"Number of Non-Zero Items..%lu", (unsigned long)tempArray.count);
}
array = [ 1, 0, 2, 0, 0, 3, 4 ]
left = 0
right = len(array) - 1
while left < right:
#If you find a non zero element while coming from the right hand side
if array[right] > 0:
#Look for an element that is 0 from the left hand side
while (left < right) and array[left] != 0:
left = left + 1
#If you find such an element, swap them
if array[left] == 0:
array[left], array[right] = array[right], array[left]
left += 1
right -= 1
#Number of non zero elements is the first index of 0
print(array.index(0))
public static int putZerosAtEnd(int[] data){
int lo = 0, hi = data.length - 1, zeros = 0;
while(lo < hi){
if(data[lo] == 0){
if(data[hi] != 0){
int temp = data[lo];
data[lo] = data[hi];
data[hi] = temp;
}else{
zeros++;
}
hi--;
}else{
lo++;
if(lo < hi && data[lo] == 0){
zeros++;
}
}
}
return zeros;
}
public static int putZerosAtEnd(int[] data){
int lo = 0, hi = data.length - 1, zeros = 0;
while(lo < hi){
if(data[lo] == 0){
if(data[hi] != 0){
int temp = data[lo];
data[lo] = data[hi];
data[hi] = temp;
}else{
zeros++;
}
hi--;
}else{
lo++;
if(lo < hi && data[lo] == 0){
zeros++;
}
}
}
return zeros;
}
language: java...we can use arraylist to store the elements and use collection.sort method to sort the elements of array in descending order...only one array is used here
def order_nonzero(input=[ 1, 0, 2, 15, 0, 0, 3, 4,0, 15 ]):
i = 0
max = len(input)
while i < max:
if input[i] == 0:
input.append(input.pop(i))
i -= 1
max -= 1
i += 1
print input
print 'total -non-zero', max
language: java...we can use arraylist to store the elements and use collection.sort method to sort the elements of array in descending order...only one array is used here
O(n) time and O(1) space
- careercupuser June 25, 2014public static int Manipulate(int[] a) { if (a.Length < 1) return 0; int i = -1, m = 0; while (m < a.Length) { if (a[m] != 0) { i += 1; a[i] = a[m]; } m++; } int count = i + 1; while (i+1 < m) { i += 1; a[i] = 0; } return count; }