{"id":25380,"date":"2017-10-15T18:12:47","date_gmt":"2017-10-15T12:42:47","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25380"},"modified":"2017-10-15T18:12:47","modified_gmt":"2017-10-15T12:42:47","slug":"java-program-count-1s-in-a-sorted-binary-array","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-count-1s-in-a-sorted-binary-array\/","title":{"rendered":"JAVA 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[ad type=\u201dbanner\u201d]\n<p>The following is JAVA implementation of above idea.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%20Java%20program%20to%20count%201\u2019s%20in%20a%20sorted%20array%0Aclass%20CountOnes%0A%7B%0A%20%20%20%20%2F*%20Returns%20counts%20of%201\u2019s%20in%20arr%5Blow..high%5D.%20%20The%0A%20%20%20%20%20%20%20array%20is%20assumed%20to%20be%20sorted%20in%20non-increasing%0A%20%20%20%20%20%20%20order%20*%2F%0A%20%20%20%20int%20countOnes(int%20arr%5B%5D%2C%20int%20low%2C%20int%20high)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20if%20(high%20%3E%3D%20low)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20get%20the%20middle%20index%0A%20%20%20%20%20%20%20%20int%20mid%20%3D%20low%20%2B%20(high%20-%20low)%2F2%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20check%20if%20the%20element%20at%20middle%20index%20is%20last%201%0A%20%20%20%20%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%0A%20%20%20%20%20%20%20%20%20%20%20%20%20(arr%5Bmid%5D%20%3D%3D%201))%0A%20%20%20%20%20%20%20%20%20%20return%20mid%2B1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20element%20is%20not%20last%201%2C%20recur%20for%20right%20side%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20%20%20return%20countOnes(arr%2C%20(mid%20%2B%201)%2C%20high)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20else%20recur%20for%20left%20side%0A%20%20%20%20%20%20%20%20return%20countOnes(arr%2C%20low%2C%20(mid%20-1))%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20CountOnes%20ob%20%3D%20new%20CountOnes()%3B%0A%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%201%2C%201%2C%201%2C%200%2C%200%2C%200%7D%3B%0A%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20System.out.println(%22Count%20of%201\u2019s%20in%20given%20array%20is%20%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ob.countOnes(arr%2C%200%2C%20n-1)%20)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201djava\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>JAVA 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":[1,2139,71670,83512],"tags":[73109,73108,70050,73099,73093,73103,73102,70843,2380,73086,72301,73096,70096,71122,72305,73083,73101,73085,73104,73107,73097,72399,72376,73082,71158,73105,70075,73087,73091,73098,71674,72380,71308,73088,72404,72299,73090,71298,73092,73084,71162,73100,73089,73094,73106,71219,2383,73095],"class_list":["post-25380","post","type-post","status-publish","format-standard","hentry","category-coding","category-java","category-searching-and-sorting","category-sorted-array","tag-append-array","tag-append-to-array","tag-array","tag-array-0","tag-array-each","tag-array-insert","tag-array-insertjava-program-count-1s-in-a-sorted-binary-array","tag-array-programming","tag-array-sort","tag-array-sort-c","tag-array-sort-java","tag-array-values","tag-arrays-binarysearch","tag-bubble-sort-java","tag-c-sort","tag-c-sort-array","tag-c-sort-function","tag-c-array-sort","tag-create-an-array","tag-index-0","tag-index-array","tag-java-array-sort","tag-java-bubble-sort","tag-java-program-count-1s-in-a-sorted-binary-array","tag-java-sort","tag-javascript-toarray","tag-linear-sort","tag-number-sorter","tag-push-array","tag-set-array","tag-sort","tag-sort-an-array","tag-sort-array","tag-sort-array-c","tag-sort-array-java","tag-sort-c","tag-sort-c-code","tag-sort-function","tag-sort-function-in-c","tag-sort-function-in-c-for-array","tag-sort-java","tag-sort-numbers","tag-sort-object","tag-sort-string","tag-sorting-in-array","tag-sorting-in-c","tag-sorting-of-array","tag-string-sort"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25380","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=25380"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25380\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25380"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25380"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25380"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}