CODEWITHSUNDEEP
algorithmmathbinary-search
ahmetbulut
ahmetbulut

Reputation: 61

find number of 1s in a 0-1 array with all 1s “on the left”?

An array consists N many 1's and 0's, all 1's come before any 0's. Find no of 1's in the array. It is clear that with binary search it is O(log N). Is there an algorithm do this in O(log(number of 1's)) time?

Upvotes: 1

Views: 233

Answers (3)

Khaled.K
Khaled.K

Reputation: 5950

class OneZero
{

    public static int binary_search (byte[] array, int start, int end, int value)
    {

        if (end <= start) return -1;

        if (Math.floor((start+end)/2) == value) return Math.floor((start+end)/2);

        return binary_search (array, start, Math.floor((start+end)/2)-1, value);

    }

    public static int nbOfOnes (byte[] array, int value)
    {

        return (binary_search(array, 0, array.length,value)+1);

    }

    public static void main ()
    {

        byte[] arr = { 1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0 };

        System.out.println(" number of 1s is: "+nbOfOnes(arr,1));

    }

}

Upvotes: 0

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37960

You can actually do it in O(lg m) time, where m is the number of 1s. I won't give the entire algorithm since this looks like homework, but here's a hint: try to "reverse" a binary search so that it expands the search area rather than contracting it.

Upvotes: 7

Iwo Kucharski
Iwo Kucharski

Reputation: 3825

If you just iterate over this array, you count all 1's and finally find 0 you made N+1 steps so it's O(n+1) algorith in my opinion.

Upvotes: 1

Related Questions