{"id":25382,"date":"2017-10-15T18:05:10","date_gmt":"2017-10-15T12:35:10","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25382"},"modified":"2017-10-15T18:05:10","modified_gmt":"2017-10-15T12:35:10","slug":"python-program-count-1s-in-a-sorted-binary-array","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-count-1s-in-a-sorted-binary-array\/","title":{"rendered":"Python 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[ad type=”banner”]\n
The following is PYTHON implementation of above idea.<\/p>\n
 
 python<\/span> <\/div> 
# Python program to count one's in a boolean array # Returns counts of 1's in arr[low..high].  The array is# assumed to be sorted in non-increasing orderdef countOnes(arr,low,high):         if high>=low:                 # get the middle index        mid = low + (high-low)\/2                 # check if the element at middle index is last 1        if ((mid == high or arr[mid+1]==0) and (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 functionarr=[1, 1, 1, 1, 0, 0, 0]print "Count of 1's in given array is",countOnes(arr, 0 , len(arr)-1) <\/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":"
PYTHON 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":[1,83517,71670,83512],"tags":[73039,73043,71869,73040,73054,73072,73060,73037,73061,73044,73035,73070,73078,73048,73032,73059,73080,73052,73034,73069,73058,73033,73056,73031,73065,73075,73041,73042,73068,73079,73049,73071,73050,73053,73073,73045,73046,73076,72758,73057,73030,73055,73074,73067,73038,73081,73036,73063,73066,73047,73077,73062,73064,73051],"class_list":["post-25382","post","type-post","status-publish","format-standard","hentry","category-coding","category-python-programming","category-searching-and-sorting","category-sorted-array","tag-append-python","tag-array-python","tag-count-python","tag-enumerate-python","tag-for-i-in-range-python","tag-list-append-python","tag-list-count-python","tag-list-python","tag-list-to-string-python","tag-python-add-to-list","tag-python-append","tag-python-append-list","tag-python-append-string","tag-python-append-to-list","tag-python-array","tag-python-array-append","tag-python-array-example","tag-python-count-items-in-list","tag-python-counter","tag-python-create-list","tag-python-empty-list","tag-python-enumerate","tag-python-find-in-list","tag-python-list","tag-python-list-add","tag-python-list-add-element","tag-python-list-append","tag-python-list-count","tag-python-list-extend","tag-python-list-find","tag-python-list-functions","tag-python-list-get","tag-python-list-index","tag-python-list-methods","tag-python-list-of-lists","tag-python-list-to-string","tag-python-matrix","tag-python-numpy-array","tag-python-print-array","tag-python-print-list","tag-python-program-count-1s-in-a-sorted-binary-array","tag-python-remove-from-list","tag-python-remove-item-from-list","tag-python-sequence","tag-python-sort-list","tag-python-split-list","tag-python-split-string","tag-python-string-append","tag-python-string-count","tag-python-string-find","tag-python-string-index","tag-python-string-to-list","tag-python-true-false","tag-string-python"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25382","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=25382"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25382\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25382"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25382"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25382"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}