Number of ones in a sorted array of zeroes and ones [closed]

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;

up vote
0
down vote

favorite

I would like to get code review for the following problem:

# Number of Ones: Given a sorted bit array (values of either 0 or 1),
# ... determine the number of 1's in the array.
# you can find the problem here: https://www.geeksforgeeks.org/find-number-zeroes/
# Parameters
# Input: arr (ints)
# Output: int

# Constraints
# Time: O(logN)
# Space: O(1)

# Examples:
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] --> 8
# [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1] --> 7
# [1, 1, 1] --> 3

def number_of_ones(arr):

 # binary search implementation
 low = 0
 high = len(arr)- 1
 while low < high:
 mid = low + (high - low) // 2
 # case when found the 1
 if arr[mid] == 1:
 high = mid
 # case when did not find the one
 else:
 low = mid + 1
 return len(arr) - low

example = number_of_ones([0, 0, 0, 0])
print (example)

edited Jul 30 at 7:57

Gareth Rees

41k394166

asked Jul 29 at 20:33

NinjaG

634221

closed as off-topic by Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger Jul 30 at 12:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." â€“ Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger

If this question can be reworded to fit the rules in the help center, please edit the question.

3

I realise that this is a learning exercise to implement binary search, so I'm not going to write an answer saying "Just use the library." But for future reference if you actually want to use a binary search in python, you want bisect docs.python.org/3/library/bisect.html
â€“Â Josiah
Jul 29 at 21:20

1

Your code does not (always) work. Consider an array of one element. low=0 and high = len(arr)-1 = 0. The while loop will not execute even once, since low is not less than high, so you return len(arr)-low = 1. Not even, you havenÃ¢Â€Â™t even looked at whether arr[0] is a zero or a one.
â€“Â AJNeufeld
Jul 29 at 21:42

5

Writing a test oracle for this problem is trivial, so randomised unit testing would surely have caught the bug spotted by AJNeufeld. (I recall giving you this advice twice previously.)
â€“Â Gareth Rees
Jul 30 at 8:36

add a commentÂ |Â

up vote
0
down vote

favorite

I would like to get code review for the following problem:

# Number of Ones: Given a sorted bit array (values of either 0 or 1),
# ... determine the number of 1's in the array.
# you can find the problem here: https://www.geeksforgeeks.org/find-number-zeroes/
# Parameters
# Input: arr (ints)
# Output: int

# Constraints
# Time: O(logN)
# Space: O(1)

# Examples:
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] --> 8
# [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1] --> 7
# [1, 1, 1] --> 3

def number_of_ones(arr):

 # binary search implementation
 low = 0
 high = len(arr)- 1
 while low < high:
 mid = low + (high - low) // 2
 # case when found the 1
 if arr[mid] == 1:
 high = mid
 # case when did not find the one
 else:
 low = mid + 1
 return len(arr) - low

example = number_of_ones([0, 0, 0, 0])
print (example)

edited Jul 30 at 7:57

Gareth Rees

41k394166

asked Jul 29 at 20:33

NinjaG

634221

closed as off-topic by Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger Jul 30 at 12:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." â€“ Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger

If this question can be reworded to fit the rules in the help center, please edit the question.

3

I realise that this is a learning exercise to implement binary search, so I'm not going to write an answer saying "Just use the library." But for future reference if you actually want to use a binary search in python, you want bisect docs.python.org/3/library/bisect.html
â€“Â Josiah
Jul 29 at 21:20

1

Your code does not (always) work. Consider an array of one element. low=0 and high = len(arr)-1 = 0. The while loop will not execute even once, since low is not less than high, so you return len(arr)-low = 1. Not even, you havenÃ¢Â€Â™t even looked at whether arr[0] is a zero or a one.
â€“Â AJNeufeld
Jul 29 at 21:42

5

Writing a test oracle for this problem is trivial, so randomised unit testing would surely have caught the bug spotted by AJNeufeld. (I recall giving you this advice twice previously.)
â€“Â Gareth Rees
Jul 30 at 8:36

add a commentÂ |Â

up vote
0
down vote

favorite

I would like to get code review for the following problem:

# Number of Ones: Given a sorted bit array (values of either 0 or 1),
# ... determine the number of 1's in the array.
# you can find the problem here: https://www.geeksforgeeks.org/find-number-zeroes/
# Parameters
# Input: arr (ints)
# Output: int

# Constraints
# Time: O(logN)
# Space: O(1)

# Examples:
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] --> 8
# [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1] --> 7
# [1, 1, 1] --> 3

def number_of_ones(arr):

 # binary search implementation
 low = 0
 high = len(arr)- 1
 while low < high:
 mid = low + (high - low) // 2
 # case when found the 1
 if arr[mid] == 1:
 high = mid
 # case when did not find the one
 else:
 low = mid + 1
 return len(arr) - low

example = number_of_ones([0, 0, 0, 0])
print (example)

edited Jul 30 at 7:57

Gareth Rees

41k394166

asked Jul 29 at 20:33

NinjaG

634221

I would like to get code review for the following problem:

# Number of Ones: Given a sorted bit array (values of either 0 or 1),
# ... determine the number of 1's in the array.
# you can find the problem here: https://www.geeksforgeeks.org/find-number-zeroes/
# Parameters
# Input: arr (ints)
# Output: int

# Constraints
# Time: O(logN)
# Space: O(1)

# Examples:
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] --> 8
# [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1] --> 7
# [1, 1, 1] --> 3

def number_of_ones(arr):

 # binary search implementation
 low = 0
 high = len(arr)- 1
 while low < high:
 mid = low + (high - low) // 2
 # case when found the 1
 if arr[mid] == 1:
 high = mid
 # case when did not find the one
 else:
 low = mid + 1
 return len(arr) - low

example = number_of_ones([0, 0, 0, 0])
print (example)

edited Jul 30 at 7:57

Gareth Rees

41k394166

asked Jul 29 at 20:33

NinjaG

634221

edited Jul 30 at 7:57

Gareth Rees

41k394166

edited Jul 30 at 7:57

Gareth Rees

41k394166

edited Jul 30 at 7:57

Gareth Rees

41k394166

asked Jul 29 at 20:33

NinjaG

634221

asked Jul 29 at 20:33

NinjaG

634221

asked Jul 29 at 20:33

NinjaG

634221

closed as off-topic by Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger Jul 30 at 12:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." â€“ Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger Jul 30 at 12:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." â€“ Gareth Rees, t3chb0t, Stephen Rauch, hjpotter92, Mathias Ettinger

If this question can be reworded to fit the rules in the help center, please edit the question.

3

I realise that this is a learning exercise to implement binary search, so I'm not going to write an answer saying "Just use the library." But for future reference if you actually want to use a binary search in python, you want bisect docs.python.org/3/library/bisect.html
â€“Â Josiah
Jul 29 at 21:20

1

Your code does not (always) work. Consider an array of one element. low=0 and high = len(arr)-1 = 0. The while loop will not execute even once, since low is not less than high, so you return len(arr)-low = 1. Not even, you havenÃ¢Â€Â™t even looked at whether arr[0] is a zero or a one.
â€“Â AJNeufeld
Jul 29 at 21:42

5

Writing a test oracle for this problem is trivial, so randomised unit testing would surely have caught the bug spotted by AJNeufeld. (I recall giving you this advice twice previously.)
â€“Â Gareth Rees
Jul 30 at 8:36

add a commentÂ |Â

3

I realise that this is a learning exercise to implement binary search, so I'm not going to write an answer saying "Just use the library." But for future reference if you actually want to use a binary search in python, you want bisect docs.python.org/3/library/bisect.html
â€“Â Josiah
Jul 29 at 21:20

1

Your code does not (always) work. Consider an array of one element. low=0 and high = len(arr)-1 = 0. The while loop will not execute even once, since low is not less than high, so you return len(arr)-low = 1. Not even, you havenÃ¢Â€Â™t even looked at whether arr[0] is a zero or a one.
â€“Â AJNeufeld
Jul 29 at 21:42

5

Writing a test oracle for this problem is trivial, so randomised unit testing would surely have caught the bug spotted by AJNeufeld. (I recall giving you this advice twice previously.)
â€“Â Gareth Rees
Jul 30 at 8:36

I realise that this is a learning exercise to implement binary search, so I'm not going to write an answer saying "Just use the library." But for future reference if you actually want to use a binary search in python, you want bisect docs.python.org/3/library/bisect.html
â€“Â Josiah
Jul 29 at 21:20

Your code does not (always) work. Consider an array of one element. low=0 and high = len(arr)-1 = 0. The while loop will not execute even once, since low is not less than high, so you return len(arr)-low = 1. Not even, you havenÃ¢Â€Â™t even looked at whether arr[0] is a zero or a one.
â€“Â AJNeufeld
Jul 29 at 21:42

Writing a test oracle for this problem is trivial, so randomised unit testing would surely have caught the bug spotted by AJNeufeld. (I recall giving you this advice twice previously.)
â€“Â Gareth Rees
Jul 30 at 8:36

add a commentÂ |Â

active

oldest

votes

搜尋此網誌

trjhtr