DSCPPAS139 - Editorial

editorial
, , ,
1

Problem Link - Number of 1s in Binary Search

Problem Statement:

You are given a sorted binary array containing 0’s and 1’s. Your task is to efficiently determine the total number of 1’s in the array.
Note: Your implementation should have a time complexity of O(log n), where ‘n’ is the length of the binary array.

Approach:

To solve this problem efficiently in O(log⁡ n) time complexity, we can use binary search to find the first occurrence of 1 in the sorted binary array. Once we find the index of the first 1, we can easily compute the total number of 1s by subtracting the index from the array length.

Steps

  • Set two pointers: low and high to the start and end of the array.
  • Use binary search to find the first occurrence of 1:
    • If the middle element is 0, move the low pointer to mid + 1.
    • If the middle element is 1, move the high pointer to mid - 1 and store the current index as the potential first 1.
  • Once the first 1 is found, compute the total number of 1s as n - index of first 1.
  • If the array contains no 1s, return 0.

Complexity:

  • Time Complexity: O(log n) Binary search uses O(log n) time complexity to search for any element in the array of size n.
  • Space Complexity: O(1) No extra Space is used .