## 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

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.

Output:

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.

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

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

here is another solution in c

having had a look at Daniel’s code, realized they are quite the same.

sorry for posting repetitive solution.

Here’s a Haskell version.

@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.

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

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])

Trying to figure out the proper way to format this…