Problem of the Day
A new programming or logic puzzle every Mon-Fri

Move Zeroes

Given a number in array form, move all the 0's to the end of the array.

[1,3,9,0,5,4,0,0,6,6,0,2,4,1,0,4,9,7,0,0,1,2,0]

Permalink: http://problemotd.com/problem/move-zeroes/

Comments:

  • yanik - 9 years, 4 months ago

    Remove from array and pop in at the end...

    $arr = [1,3,9,0,5,4,0,0,6,6,0,2,4,1,0,4,9,7,0,0,1,2,0]
    $zero_bucket = []
    
    $arr.delete_if do |x|
      if x == 0
        $zero_bucket << x
        true
      end
    end
    
    $zero_bucket.each {|x| $arr << x}
    
    p $arr
    

    reply permalink

  • Anonymous - 9 years, 4 months ago

    #python
    def movezeros(za):
        for item in za:
            if item == 0:
                za.remove(item)
                za.append(item)
        return za
    

    reply permalink

  • Daniel - 9 years, 3 months ago

    You can do it in-place in O(n+k) where k is the length of the largest consecutive run of zeros.

    int[] arr = {1,3,9,0,5,4,0,0,6,6,0,2,4,1,0,4,9,7,0,0,1,2,0};
    
    int c = 0;
    for(int i = 0; i < arr.length; i++) {
        while(i+c < arr.length && arr[i+c] == 0)
            c++;
        if(c == 0) continue;
    
        while(i+c < arr.length && arr[i+c] == 0)
            c++;
    
        if(i+c >= arr.length)
            arr[i] = 0;
        else
            arr[i] = arr[i + c];
    }
    

    reply permalink

  • Daniel - 9 years, 3 months ago

    Sorry I meant to say O(n*k) not O(n+k)

    reply permalink

Content curated by @MaxBurstein