{"id":25381,"date":"2017-10-15T18:03:13","date_gmt":"2017-10-15T12:33:13","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25381"},"modified":"2017-10-15T18:03:13","modified_gmt":"2017-10-15T12:33:13","slug":"c-program-count-1s-in-a-sorted-binary-array-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-count-1s-in-a-sorted-binary-array-2\/","title":{"rendered":"C++ Program Count 1\u2019s in a sorted binary array"},"content":{"rendered":"

Given a binary array sorted in non-increasing order, count the number of 1\u2019s in it.<\/span><\/p>\n

Examples:<\/p>\n

Input: arr[] = {1, 1, 0, 0, 0, 0, 0}\r\nOutput: 2\r\n\r\nInput: arr[] = {1, 1, 1, 1, 1, 1, 1}\r\nOutput: 7\r\n\r\nInput: arr[] = {0, 0, 0, 0, 0, 0, 0}\r\nOutput: 0\r\n<\/pre>\n
A simple solution is to linearly traverse the array. The time complexity of the simple solution is O(n). We can use Binary Search <\/a>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.<\/p>\n
The following is C++ implementation of above idea.<\/p>\n
 
 C++<\/span> <\/div> 
\/\/ 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;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Count of 1's in given array is 4<\/pre>\n
Time complexity of the above solution is O(Logn)<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C++ Program Count 1\u2019s in a sorted binary array – Searching and Sorting – 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. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,71670,83512],"tags":[70276,72825,70812,70052,70304,70076,73117,70107,70120,73122,70082,70270,70113,70086,70265,70320,73112,73111,70316,73114,72824,73124,73120,70116,72724,73113,72690,73110,70496,70018,70083,70117,70070,70761,73123,73119,73127,70286,73115,70073,73118,73116,70308,70826,73128,70813,73126,73121,73125],"class_list":["post-25381","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-searching-and-sorting","category-sorted-array","tag-algorithm-for-binary-search","tag-array-declaration-c","tag-array-in-c-programming","tag-binary-search","tag-binary-search-algorithm-in-c","tag-binary-search-c","tag-binary-search-c-code","tag-binary-search-c-program","tag-binary-search-code","tag-binary-search-code-c","tag-binary-search-example","tag-binary-search-in-c","tag-binary-search-in-c-program","tag-binary-search-program","tag-binary-search-program-in-c","tag-binary-search-program-in-c-using-function","tag-binary-search-program-in-c-with-output","tag-binary-search-using-array-in-c","tag-binary-sort-in-c","tag-c-2d-array-initialization","tag-c-array-size","tag-c-binary","tag-c-code-for-binary-search","tag-c-program-for-binary-search","tag-c-program-to-search-an-element-in-an-array","tag-c-search-algorithms","tag-c-binary-search","tag-c-program-count-1s-in-a-sorted-binary-array","tag-linear-search","tag-linear-search-algorithm","tag-linear-search-c-program","tag-linear-search-in-c-program","tag-linear-search-program","tag-linear-search-program-in-c","tag-one-dimensional-array-c","tag-one-dimensional-array-c-example-program","tag-printf-array","tag-program-for-binary-search","tag-program-for-binary-search-in-c","tag-program-for-linear-search","tag-program-of-binary-search","tag-program-of-binary-search-in-c","tag-searching-c","tag-wap-in-c","tag-wap-in-search","tag-what-is-array-in-c","tag-write-a-program-to-search-an-element-in-an-array","tag-write-ac-program-for-linear-search","tag-write-ac-program-to-implement-binary-search-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25381","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25381"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25381\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}