Count ones in a sorted binary array in Java
Introduction:
Counting ones in a sorted binary array is a common problem in computer science and algorithmic programming. The problem statement typically involves finding the number of occurrences of the digit '1' in a sorted array consisting of only 0s and 1s. The array is sorted, which means that all the 0s appear before all the 1s.
Example 1:
Input: [0,0,0,1,1]
Output: 2
Explanation: Total number of 1's in given array is 2, so the answer will be 2
Example 2:
Input: [0,0,0,0,0,0,1]
Output: 1
Explanation: Total number of 1’s in given array is 1
Approach: Brute-force Approach
The brute-force approach to count ones in a sorted binary array is a simple and straightforward method that involves iterating through the entire array and counting the number of occurrences of '1'. While it's not the most efficient approach, it's easy to understand and implement.
Algorithm:
Step 1: Initialize a variable count to 0. This variable will be used to keep track of the number of ones.
Step 2: Iterate through each element of the array arr from the first element (index 0) to the last element (index arr.length - 1) using a for loop.
Step 3: For each element at index i in the array:
Step 3.1: Check if the current element arr[i] is equal to 1.
Step 3.2: If arr[i] is equal to 1, increment the count variable by 1.
Step 4: After iterating through the entire array, the count variable will contain the total count of ones in the binary array.
Step 5: Return the value of count as the final result.
Filename: CountOnesInSortedBinaryArray.java
public class CountOnesInSortedBinaryArray {
public static int countOnes(int[] arr) {
// Initialize a counter to keep track of the number of ones
int count = 0;
// Iterate through the entire array
for (int i = 0; i < arr.length; i++) {
// Check if the current element is '1'
if (arr[i] == 1) {
// If it is '1', increment the count
count++;
}
}
// Return the final count, which represents the number of ones in the array
return count;
}
public static void main(String[] args) {
// Sample binary array
int[] binaryArray = {0, 0, 1, 1, 1, 1, 1};
// Call the countOnes function to count the ones in the binary array
int onesCount = countOnes(binaryArray);
// Print the result
System.out.println("Number of ones in the binary array: " + onesCount);
}
}
Output:
Number of ones in the binary array: 5
Time Complexity:
The time complexity of this approach is O(n), where 'n' is the size of the input array. This is because the algorithm iterates through each element in the array exactly once to count the ones. The time complexity is linear with respect to the size of the input.
Space Complexity:
The space complexity of this approach is O(1), which means it uses constant space. Regardless of the size of the input array, the algorithm only uses a fixed amount of memory to store the count variable. It doesn't create additional data structures or allocate memory that grows with the input size. Therefore, the space complexity is constant.
Approach: Using Binary Search
The Efficient Binary Search-Based Approach to count ones in a sorted binary array is a more optimized algorithm compared to the brute-force approach. It leverages the fact that the input array is sorted and uses a binary search technique to find the first occurrence of '0' in the array, which in turn gives us the count of ones. This approach has a time complexity of O(log n), making it significantly faster for large arrays.
Algorithm:
Step 1: Initialize two pointers, left and right, to represent the current search interval. left starts at the beginning of the array (index 0), and right starts at the end of the array (index arr.length - 1).
Step 2: Enter a loop that continues until left is less than or equal to right. This loop effectively narrows down the search space.
Step 3: Inside the loop, calculate the middle index mid as left + (right - left) / 2.
Step 3.1: Check the value of arr[mid], if arr[mid] is equal to 1, it means we haven't encountered a '0' yet, so we move the left pointer to mid + 1 to search in the right subarray.
Step 3.2: If arr[mid] is equal to 0, it means we have found the first '0' in the array. We update the right pointer to mid - 1 to continue searching for '0's in the left subarray.
Step 4: Repeat steps 3 until left is no longer less than or equal to right.
Step 5: The left pointer now represents the index of the first '0' in the array. Since the array is sorted, the count of ones before this index is equal to the index itself.
Step 6: Return the value of left as the count of ones in the binary array.
Filename: CountOnesInSortedBinaryArray1.java
public class CountOnesInSortedBinaryArray1 {
public static int countOnes(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if the middle element is 1
if (arr[mid] == 1) {
// If it is 1, move the right pointer to the left subarray
right = mid - 1;
} else {
// If it is 0, move the left pointer to the right subarray
left = mid + 1;
}
}
// The 'left' pointer now represents the index after the last '1'
// The count of ones is equal to the length of the array minus the index 'left'
return arr.length - left;
}
public static void main(String[] args) {
int[] binaryArray = {0, 0, 1, 1, 1, 1, 1};
int onesCount = countOnes(binaryArray);
System.out.println("Number of ones in the binary array: " + onesCount);
}
}
Output:
Number of ones in the binary array: 5
Time Complexity:
The time complexity of this approach is O(log n), where 'n' is the size of the input array. This is because the algorithm uses binary search to divide the search space in half with each iteration. As a result, it efficiently narrows down the search space and finds the index of the first '0' in logarithmic time, making it significantly faster than the brute-force approach.
Space Complexity:
The space complexity of this approach is O(1), which means it uses constant space. Regardless of the size of the input array, the algorithm only uses a fixed amount of memory for a few integer variables (left, right, mid, etc.). It doesn't create additional data structures or allocate memory that grows with the input size. Therefore, the space complexity is constant.
Approach: Count Ones Using Linear Scan and Two-Pointers
The "Count Ones Using Linear Scan and Two-Pointers" approach is a method to count the number of ones in a sorted binary array. This approach utilizes two pointers that start from both ends of the array and move towards each other while incrementing a count variable for each '1' encountered. When the pointers meet or cross over each other, the counting process stops. This method is efficient when there is a significant number of ones in the array and avoids scanning the entire array when the first '0' is encountered.
Algorithm:
Step 1: Initialize three variables, left: A pointer starting from the beginning (index 0) of the array, right: A pointer starting from the end (index arr.length - 1) of the array, count: A variable to keep track of the number of ones, initially set to 0.
Step 2: Enter a loop that continues until left is less than or equal to right. This loop effectively narrows down the search space.
Step 3: Inside the loop, perform the following steps, check if arr[left] is equal to 1. If it is, increment the count variable by 1.
Step 3.1: Check if arr[right] is equal to 1. If it is, increment the count variable by 1. Move the left pointer one step to the right (increment left) and move the right pointer one step to the left (decrement right).
Step 4: Continue steps 3 until left is greater than right or they meet.
Step 5: If left and right meet on the same element (in the case of an odd-length array), check if that element is 1. If it is, increment the count variable by 1.
Step 6: Return the final value of the count, which represents the count of ones in the binary array.
Filename: CountOnesInSortedBinaryArray2.java
public class CountOnesInSortedBinaryArray2 {
public static int countOnes(int[] arr) {
int left = 0;
int right = arr.length - 1;
int count = 0;
while (left <= right) {
if (arr[left] == 1) {
count++; // Increment count if '1' is encountered on the left
left++; // Move the left pointer to the right
} else if (arr[right] == 1) {
count++; // Increment count if '1' is encountered on the right
right--; // Move the right pointer to the left
} else {
break; // Exit the loop when '0' is encountered on both sides
}
}
return count;
}
public static void main(String[] args) {
int[] binaryArray = {0, 0, 1, 1, 1, 1, 1};
int onesCount = countOnes(binaryArray);
System.out.println("Number of ones in the binary array: " + onesCount);
}
}
Output:
Number of ones in the binary array: 5
Time Complexity:
The time complexity of this approach is O(n), where 'n' is the size of the input array. In the worst case, when all elements of the array are '1', the algorithm will perform a complete linear scan of the array. This is because it needs to examine each element at least once to determine whether it's a '0' or '1'. In practice, it may exit early when '0' is encountered on both sides.
Space Complexity:
The space complexity of this approach is O(1), which means it uses constant space. Regardless of the size of the input array, the algorithm only uses a fixed amount of memory for a few integer variables (left, right, count) and does not create additional data structures or allocate memory that grows with the input size. Therefore, the space complexity is constant.