{"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":"<p>Given a binary array sorted in non-increasing order, count the number of 1\u2019s in it.<span id=\"more-142561\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>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<p>A simple solution is to linearly traverse the array. The time complexity of the simple solution is O(n). We can use <a href=\"http:\/\/quiz.geeksforgeeks.org\/binary-search\/\" target=\"_blank\" rel=\"noopener noreferrer\">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<p>The following is C++ implementation of above idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20count%20one\u2019s%20in%20a%20boolean%20array%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20Returns%20counts%20of%201\u2019s%20in%20arr%5Blow..high%5D.%20%20The%20array%20is%0A%20%20%20assumed%20to%20be%20sorted%20in%20non-increasing%20order%20*%2F%0Aint%20countOnes(bool%20arr%5B%5D%2C%20int%20low%2C%20int%20high)%0A%7B%0A%20%20if%20(high%20%3E%3D%20low)%0A%20%20%7B%0A%20%20%20%20%2F%2F%20get%20the%20middle%20index%0A%20%20%20%20int%20mid%20%3D%20low%20%2B%20(high%20-%20low)%2F2%3B%0A%20%0A%20%20%20%20%2F%2F%20check%20if%20the%20element%20at%20middle%20index%20is%20last%201%0A%20%20%20%20if%20(%20(mid%20%3D%3D%20high%20%7C%7C%20arr%5Bmid%2B1%5D%20%3D%3D%200)%20%26%26%20(arr%5Bmid%5D%20%3D%3D%201))%0A%20%20%20%20%20%20return%20mid%2B1%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20element%20is%20not%20last%201%2C%20recur%20for%20right%20side%0A%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%201)%0A%20%20%20%20%20%20return%20countOnes(arr%2C%20(mid%20%2B%201)%2C%20high)%3B%0A%20%0A%20%20%20%20%2F%2F%20else%20recur%20for%20left%20side%0A%20%20%20%20return%20countOnes(arr%2C%20low%2C%20(mid%20-1))%3B%0A%20%20%7D%0A%20%20return%200%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20bool%20arr%5B%5D%20%3D%20%7B1%2C%201%2C%201%2C%201%2C%200%2C%200%2C%200%7D%3B%0A%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20cout%20%3C%3C%20%22Count%20of%201\u2019s%20in%20given%20array%20is%20%22%20%3C%3C%20countOnes(arr%2C%200%2C%20n-1)%3B%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Count of 1's in given array is 4<\/pre>\n<p>Time complexity of the above solution is O(Logn)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C++ Program Count 1\u2019s in a sorted binary array &#8211; Searching and Sorting &#8211; 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}]}}