Zeros And Ones

October 17, 2017

Zeros And Ones

This is somebody’s homework problem:

Given an array containing only zeros and ones, find the index of the zero that, if converted to one, will make the longest sequence of ones. For instance, given the array [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1], replacing the zero at index 10 (counting from 0) forms a sequence of 9 ones.

Your task is to write a program that determines where to replace a zero with a one to make the maximum length subsequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

10 Responses to “Zeros And Ones”

  1. Daniel said

    Here’s a solution in C99. The algorithm is O(n) time, O(1) space. It considers sub arrays have three zeros, one on each end. It returns the second zero of the longest such sub array. For the algorithm to work properly, indices -1 and n are treated as if there were zeros there.

    /* zeros_and_ones.c */
    
    #include <stdio.h>
    
    int replace_idx(int* array, int n) {
        int idx0 = -1;
        int idx1 = -1;
        int idx2 = -1;
        int max_length = 0;
        int max_idx = -1;
        for (int i = 0; i <= n; ++i) {
            int val = 0;
            if (i != n) val = array[i];
            if (val == 0) {
                idx0 = idx1;
                idx1 = idx2;
                idx2 = i;
                int length = idx2 - idx0 - 1;
                if (length > max_length) {
                    max_length = length;
                    max_idx = idx1;
                }
            }
        }
        return max_idx;
    }
    
    int main(int argc, char* argv[]) {
        int array[] = {1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1};
        int n = sizeof(array) / sizeof(int);
        printf("%d\n", replace_idx(array, n));
    }
    

    Output:

    $ c99 -g -Wall -o zeros_and_ones zeros_and_ones.c
    $ ./zeros_and_ones
    
    10
    
  2. Daniel said

    Clarification: It considers sub arrays that have three zeros, with one of the zeros at the beginning and one of the zeros at the end.

  3. Daniel said

    Clarification: It returns the index of the second zero of the longest such sub array (index with respect to the entire input array).

  4. Himanshu said

    How do we know the number of total characters that is 1 and 0 the array contains?

  5. isaac said

    here is another solution in c

    #include <stdio.h>
    
    int main() {
    
        int d[] = {1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1};
        int d_size = sizeof(d)/sizeof(int);
        int i = 0;
        int best_zero_index = -1;   //holds the answer
        int prev_zero_index = -1;   //holds previous zero index
        int post_zero_streak = 0;   //number of ones after a zero
        int pre_zero_streak = 0;    //number of ones before a zero
        int max_ones_streak = 0;    //holds maximum ones streak length
    
        for(i = 0; i <= d_size; i++) {  //from 0 to sizeof(d) + 1, last enumartion supposes the array ends with zero
    
            if(i == d_size || d[i] == 0) {
                if((pre_zero_streak + post_zero_streak + 1) >= max_ones_streak) {   //checks for a better answer
                    best_zero_index = prev_zero_index;
                    max_ones_streak = pre_zero_streak + post_zero_streak + 1;
                }
    
                pre_zero_streak = post_zero_streak;
                post_zero_streak = 0;
                prev_zero_index = i;
            }
    
            else {
                post_zero_streak += 1;
            }
    
        }
    
        printf("best zero index:%d\n", best_zero_index);
        return 0;
    }
    
  6. isaac said

    having had a look at Daniel’s code, realized they are quite the same.
    sorry for posting repetitive solution.

  7. Globules said

    Here’s a Haskell version.

    -- Find the index of an element, whose value is 0, which if set to 1 would
    -- maximize the length of a run of 1s.
    -- 
    -- Let ns = [n(0), n(1), ..., n(N-1)] be a list of 0s and 1s of length N, and
    -- let is = [i(0) = 0, i(1), i(2), ..., i(m), i(m+1) = N], be the indices of all
    -- the 0 elements of ns.  (Only i(j), for 1 ≤ j ≤ m, refer to actual elements of
    -- ns.)  We have:
    --
    --   - the length of the run of 1s preceding i(j) is i(j)-i(j-1)-1
    --   - the length of the run of 1s following i(j) is i(j+1)-i(j)-1
    --
    -- The length of the run of 1s created by setting i(j) to 1 would be:
    --
    --   i(j)-i(j-1)-1 + 1 + i(j+1)-i(j)-1
    -- 
    -- Therefore, we want to find the i(j), 1 ≤ j ≤ m, that maximizes:
    --
    --   i(j)-i(j-1)-1+1+i(j+1)-i(j)-1, or
    --   -i(j-1)+i(j+1)-1, or
    --   i(j+1)-i(j-1)-1, or
    --   i(j+1)-i(j-1)
    
    import Data.List (elemIndices)
    
    -- The value of `replaceIdx ns' is the zero-based index of ns where setting a 0
    -- to 1 would result in the longest run of 1s in ns.  If ns contains no 0s then
    -- return nothing.  If there is more than one index that would result in runs of
    -- the same length, then return the greatest.
    longestRunIdx :: [Int] -> Maybe Int
    longestRunIdx ns = go $ 0 : elemIndices 0 ns ++ [length ns]
      where go [_,_] = Nothing
            go is    = Just . snd . maximum $ lenIdxs is
            lenIdxs is = zipWith3 (\x j y -> (y-x, j)) is (drop 1 is) (drop 2 is)
    
    main :: IO ()
    main = do
      print $ longestRunIdx []
      print $ longestRunIdx [1]
      print $ longestRunIdx [1,1]
      print $ longestRunIdx [0,1,1]
      print $ longestRunIdx [1,0,1]
      print $ longestRunIdx [1,1,0]
      print $ longestRunIdx [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1]
    
    $ ./longrun 
    Nothing
    Nothing
    Nothing
    Just 0
    Just 1
    Just 2
    Just 10
    
  8. Globules said

    @Himanshu I don’t think we should need to know any of those things. The array could be empty (i.e. have 0 length), it could be all 0s, all 1s, or any combination of 0s and 1s.

  9. David Liu said

    Here’s a python solution:

    Zeros and Ones

    Given an array containing only zeros and ones, find the index of the zero that, if converted to one, will make the longest sequence of ones. For instance, given the array [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1], replacing the zero at index 10 (counting from 0) forms a sequence of 9 ones.

    Array1 = [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1]

    print(“Initial array:”, Array1)

    Step 1: Find indicies of all Zeros in Array1

    L = len(Array1)
    zeros = []

    for i in range(L):
    if Array1[i] == 0:
    zeros.append(i)

    print(“Indicies of all zeros:”, zeros)

    Step 2: Number of Ones before and after each zero is equal to differences in index values to the next and previous zero minus one.

    L_z = len(zeros)

    before = []
    after = []
    total = []

    for i in range(L_z):
    if i == 0: # The number of ones before the first zero is equal to its index
    valb = zeros[i]
    vala = zeros[i+1]-zeros[i]-1
    elif i == (L_z-1): # The number of ones after the last zero is equal to its index minus array length minus one.
    vala = L-zeros[i]-1
    valb = zeros[i]-zeros[i-1]-1
    else:
    valb = zeros[i]-zeros[i-1]-1
    vala = zeros[i+1]-zeros[i]-1

    before.append(valb)
    after.append(vala)
    total.append(vala+valb)
    

    print(“Number of Ones before each Zero:”, before)
    print(“Number of Ones after each Zero:”, after)
    print(“Number of Ones before AND after each Zero:”, total)

    Step 3: Find index of maximum value

    index_max = total.index(max(total))

    print(“\nThe zero to replace is in index number”,zeros[index_max])

  10. David Liu said

    Trying to figure out the proper way to format this…

    # Zeros and Ones
    # Given an array containing only zeros and ones, find the index of the zero that, if converted to one, will make the longest sequence of ones. For instance, given the array [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1], replacing the zero at index 10 (counting from 0) forms a sequence of 9 ones.
    
    Array1 = [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1]
    
    print("Initial array:", Array1)
    
    # Step 1: Find indicies of all Zeros in Array1
    
    L = len(Array1)
    zeros = []
    
    for i in range(L):
        if Array1[i] == 0:
            zeros.append(i)
    
    print("Indicies of all zeros:", zeros)
    
    
    # Step 2: Number of Ones before and after each zero is equal to differences in index values to the next and previous zero minus one.
    
    L_z = len(zeros)
    
    before = []
    after = []
    total = []
    
    for i in range(L_z):
        if i == 0:  # The number of ones before the first zero is equal to its index
            valb = zeros[i]
            vala = zeros[i+1]-zeros[i]-1
        elif i == (L_z-1): # The number of ones after the last zero is equal to its index minus array length minus one.
            vala = L-zeros[i]-1
            valb = zeros[i]-zeros[i-1]-1
        else:
            valb = zeros[i]-zeros[i-1]-1
            vala = zeros[i+1]-zeros[i]-1
    
        before.append(valb)
        after.append(vala)
        total.append(vala+valb)
    
    print("Number of Ones before each Zero:", before)
    print("Number of Ones after each Zero:", after)
    print("Number of Ones before AND after each Zero:", total)
    
    # Step 3: Find index of maximum value
    
    index_max = total.index(max(total))
    
    print("\nThe zero to replace is in index number",zeros[index_max])
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: