{"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":"

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 JAVA implementation of above idea.<\/p>\n
 
 java<\/span> <\/div> 
\/ Java program to count 1's in a sorted arrayclass CountOnes{    \/* Returns counts of 1's in arr[low..high].  The       array is assumed to be sorted in non-increasing       order *\/    int countOnes(int 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 *\/    public static void main(String args[])    {       CountOnes ob = new CountOnes();       int arr[] = {1, 1, 1, 1, 0, 0, 0};       int n = arr.length;       System.out.println("Count of 1's in given array is " +                           ob.countOnes(arr, 0, n-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":"
JAVA 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,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}]}}