For this problem and the next you may use any of the algorithms developed in cla
ID: 3840568 • Letter: F
Question
For this problem and the next you may use any of the algorithms developed in class as subroutines. Just be sure to specify the input to the algorithm, and what operation is performed. For instance, prefix "sum" can be used as prefix SUM, or prefix MULT, or prefix MAX, etc.
a) Give an O(log n) time, O(n) work EREW algorithm, which, given a boolean array A of size n, writes into location FIRST. the smallest index k such that A[k] = 1. You may assume that such a k exists. Also, your solution should not change array A (i.e. you will need to do any computation in another array). Recall that a boolean array is one where all values are 0 or 1.
b) Give an O(1) time, O(n2) work common CRCW algorithm for the same problem.
Explanation / Answer
Given a binary array sorted in non-increasing order, count the number of 1’s in it.
Examples:
Input: arr[] = {1, 1, 0, 0, 0, 0, 0}
Output: 2
Input: arr[] = {1, 1, 1, 1, 1, 1, 1}
Output: 7
Input: arr[] = {0, 0, 0, 0, 0, 0, 0}
Output: 0
A simple solution is to linearly traverse the array. The time complexity of the simple solution is O(n). We can use Binary Search to find count in O(Logn) time. The idea is to look for last occurrence of 1 using Binary Search. Once we find the index last occurrence, we return index + 1 as count.
The following is C++ implementation of above idea.
C++PythonJava
// C++ program to count one's in a boolean array
#include <iostream>
using namespace std;
/* Returns counts of 1's in arr[low..high]. The array is
assumed to be sorted in non-increasing order */
int countOnes(bool arr[], int low, int high)
{
if (high >= low)
{
// get the middle index
int mid = low + (high - low)/2;
// check if the element at middle index is last 1
if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
return mid+1;
// If element is not last 1, recur for right side
if (arr[mid] == 1)
return countOnes(arr, (mid + 1), high);
// else recur for left side
return countOnes(arr, low, (mid -1));
}
return 0;
}
/* Driver program to test above functions */
int main()
{
bool arr[] = {1, 1, 1, 1, 0, 0, 0};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of 1's in given array is " << countOnes(arr, 0, n-1);
return 0;
}
Output:
Count of 1's in given array is 4
Time complexity of the above solution is O(Logn)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.