CareerCup

Binary search the array, get the leftest element of k and the rightest element of k. Minus their positions.
Here is the c++ code:

#include <iostream>
using namespace std;

int left(int *array, int k, int start, int end)
{
    if (start > end)
    {
        return -1;
    }
    while (start < end)
    {
        int mid = start + (end - start) / 2;
        if (array[mid] == k)
        {
            end = mid;
        }
        else if (array[mid] > k)
        {
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }
    if (array[start] == k)
    {
        return start;
    }
    return -1;
}

int right(int *array, int k, int start, int end)
{
    if (start > end)
    {
        return -1;
    }
    if (start == end)
    {
        if (array[start] == k)
        {
            return start;
        }
        else
        {
            return -1;
        }
    }
    while (start < end - 1)
    {
        int mid = start + (end - start) / 2;
        if (array[mid] == k)
        {
            start = mid;
        }
        else if (array[mid] > k)
        {
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }
    if (array[end] == k)
    {
        return end;
    }
    if (array[start] == k)
    {
        return start;
    }
    return -1;
}

int main()
{
    int n, k;
    int array[1000];
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        cin >> array[i];
    }
    int l = left(array, k, 0, n - 1);
    if (l == -1)
    {
        cout << "no such element" << endl;
        return 0;
    }
    int r = right(array, k, 0, n - 1);
    cout << r - l + 1 << endl;
    return 0;
}

Number of occurrences on n in array = upper_bound(arr, arr + sz, n) - lower_bound(arr, arr+ sz, n);

// assume sz = size of array.

<pre lang="" line="1" title="CodeMonkey65921" class="run-this">import java.util.Arrays;

class CountTheDuplicate {

public int findOcurance(int[] arr, int key) {
if (arr == null || arr.length == 0) {
return 0;
}

// find the index of first element matching the key
int lowBound = findBound(arr, key);
if (lowBound == -1) {
return 0;
}

// find the index of last element matching the key
int highBound = findBound(arr, key, lowBound, arr.length - 1, false);

return highBound - lowBound + 1;
}

private int findBound(int[] arr, int key) {
return findBound(arr, key, 0, arr.length, true);
}

private int findBound(int[] arr, int key, int low, int high,
boolean forLowBound) {
while (low <= high) {
int mid = low + high >> 1;
int midVal = arr[mid];
if (midVal < key) {
low = mid + 1;
} else if (midVal > key) {
high = mid - 1;
} else {
/*
* Expanded equal case handling to directly pinpoint the
* range of equal elements by peeking into neighbor element
* (previous for low bound or next for high bound).
*
*/
if (forLowBound) {
if (mid == 0) {
return 0; // low bound found
}
if (arr[mid - 1] < key) {
return mid; // low bound found}
}
high = mid - 1;
} else {
if (mid == arr.length - 1) {
return arr.length - 1; // high bound found
}
if (arr[mid + 1] > key) {
return mid; // high bound found}
}
low = mid + 1;
}
}
}
return -1; // key not found.
}

public static void main(String[] args) {
int[] arr = new int[] { 2, 2, 4, 5, 5, 5, 5, 9, 11, 12, 12, 13, 14, 20,23, 24, 24, 26, 26, 28 };
CountTheDuplicate co = new CountTheDuplicate();
System.out.println(Arrays.toString(arr));
for (int key : new int[] { 1, 2, 5, 12, 14, 21, 28, 100 }) {
System.out.println(key + " occurs " + co.findOcurance(arr, key)
+ " times.");
}
}
}

</pre>

searching for a element in sorted array tkes O(logn)...and all occurrences of n should be in consecutive array elements...is that all...or am I missing something?

it can be done by using a variation of binary search. once the elemnt is found in O(log n) check the consecutive elements to the right and left till a non-match is found, and increment the counter.

it can be done by using a variation of binary search. once the elemnt is found in O(log n) check the consecutive elements to the right and left till a non-match is found, and increment the counter.

int CountFreq (int *A, int value, int low, int high)
{
int mid;
if (high < low)
return 0;
mid = low + (high - low);
if (A[mid] > value)
return CountFreq (A, value, low, mid - 1);
else if (A[mid] < value)
return CountFreq (A, value, mid + 1, high);
else
return 1 + CountFreq (A, value, low, mid - 1) + CountFreq (A, value, mid + 1, high);
}

int main() {

int A[6] = { 1, 2, 3, 3, 3, 4};
int value = 3;

int count = 0;

printf("%d\n", CountFreq(A, value, 0, sizeof(A)/sizeof(int)-1));

return 0;

}

1. Conduct binary search for an element witch equals to n and its previous element is equal to or less than n-1, taking the possibility that element being checked is the first element in the array into account.

2. Conduct binary search for an element witch equals to n and its next element is equal to or larger than n+1, taking the possibility that element being checked is the last element in the array into account.

3. From the result of step and step 2, figure out the occurance of n.

Since it costs two binary search regardless how many times n appears, it is an O(logn) solution.

<pre lang="" line="1" title="CodeMonkey30344" class="run-this">import java.util.Arrays;

public class CountTheDuplicate {

public int findOcurance(int[] arr, int key) {
if (arr == null || arr.length == 0) {
return 0;
}

int lowBound = findBound(arr, key, 0, arr.length - 1, true);
int highBound = findBound(arr, key, 0, arr.length - 1, false);
return lowBound == -1 ? 0 : highBound - lowBound + 1;
}

private int findBound(int[] arr, int key, int low, int high,
boolean forLowBound) {
while (low <= high) {
int mid = low + high >> 1;
int midVal = arr[mid];
if (midVal < key) {
low = mid + 1;
} else if (midVal > key) {
high = mid - 1;
} else {
if (forLowBound) {
if (mid == 0) {
return 0; // low bound found
}
if (arr[mid - 1] < key) {
return mid; // low bound found}
}
high = mid - 1;
} else {
if (mid == arr.length - 1) {
return arr.length - 1; // high bound found
}
if (arr[mid + 1] > key) {
return mid; // high bound found}
}
low = mid + 1;
}
}
}
return -1; // key not found.
}

public static void main(String[] args) {
int[] arr = new int[] { 2, 2, 4, 5, 5, 5, 5, 9, 11, 12, 12, 13, 14, 20,
23, 24, 24, 26, 26, 28 };
CountTheDuplicate ro = new CountTheDuplicate();
System.out.println(Arrays.toString(arr));
for (int key : new int[] { 1, 2, 5, 12, 14, 21, 28, 100 }) {
System.out.println(key + " occurs "
+ ro.findOcurance(arr, key) + " times.");
}
}
}</pre>

<pre lang="" line="1" title="CodeMonkey32379" class="run-this">In the code above, if the lowBound is -1, there is no need go any further. On the other hand, if lowBound is not -1, the search for highBound can be narrowed down to from lowBound to arr.length - 1. Given these, the findOcurance method can be improved as:


public int findOcurance(int[] arr, int key) {
if (arr == null || arr.length == 0) {
return 0;
}

int lowBound = findBound(arr, key, 0, arr.length - 1, true);
if (lowBound == -1) {
return 0;
}
return findBound(arr, key, lowBound, arr.length - 1, false) - lowBound + 1;
}
</pre>

<pre lang="" line="1" title="CodeMonkey8647" class="run-this">public static int FindOccurance(int[] arr, int n, int left, int right)
{
if(left > right) return 0;

int p = (left + right) / 2;
if (arr[p] > n)
return FindOccurance(arr, n, left, p - 1);
if(arr[p] < n)
return FindOccurance(arr, n, p + 1, right);

return 1 + ((p > left) ? FindOccurance(arr, n, left, p - 1) : 0) +((p < right) ? FindOccurance(arr, n, p + 1, right) : 0); }

int[] arr = { 1,2,3,4,4,4,4,4,5,6,7,8,9,10 };
Console.WriteLine(FindOccurance(arr, 4, 0, arr.Length - 1));
</pre><pre title="CodeMonkey8647" input="yes">
</pre>

yes algo will run O(logn) if there is 1 ocurance the worst case is O(n). but I don"t it is posible to find O(logn) for the worst case

Please code below:
simple algo work in O(log n) in all cases
Search element using binary search
keep start_index = end_index = searched_index (si = ei = i)
now search leftmost index using binary search (si = i)
again search rightmost index using binary search (ei = i)
print si & ei

Need to do 3 Binary searches.

1. Find the index for N. (at this stage you will have Low, N, High
2. Find Index of first between low-N and last N between N-High

takes O(logn)

- binary search for 'n' takes logn, say teh number 'x' found at index 'i'
- do a binary search between 'low' and 'i' for the number which is less than 'x'. you got the index 'i1'
- do a binary search between 'i' and 'high' for the number which is grater than 'x'. you got the index 'i2'
- so total occurances are i2-i1+1

I get a 0(logn) method.

Maybe we can use a floating number array to store the integers.

To count a integer n, we only need two binary search for n-0.5 and n+0.5.
The binary search return the position of the smallest integet larger than n-0.5, which is the position of the first n, and the position of the smallest integer larger than n+0.5, which is also the position of the first smallest integet larget than n.
Substracting pos1 from pos2, we get the count.

This method appriciate the following conclusion: If a number is not in the sorted array, when the algorithm terminates, (right,left) or (-inf,left) or (right,inf) will be the range for the number.

Do binary search for (n-1) and (n+1), the indexes are lower and upper bound of occurrences of n.
Which is O(nlogn)

For corner case, where all elements are same, check first and last elements, which is O(1).

public class NumberOfOccurences {

	private void findNumOfOccurences(int[] arr, int element) {
		int low = 0;
		int high = arr.length - 1;
		int leftIndex = getLeftIndex(arr, element, low, high);
		System.out.println("Element : " + element);
		if (leftIndex == -1) {
			System.out.println("No such element exists");
			return;
		}
		System.out.println("Left Index : " + leftIndex);
		int rightIndex = getRightIndex(arr, element, leftIndex + 1, high);
		if (rightIndex == -1) {
			System.out.println("No of occurences : " + 1);
			return;
		}
		System.out.println("Right Index : " + rightIndex);
		System.out
				.println("No of occurences : " + (rightIndex - leftIndex + 1));
	}

	private int getLeftIndex(int[] arr, int element, int low, int high) {
		int pos = 0;
		if (high >= low) {
			int mid = (low + high) / 2;
			if (arr[mid] < element) {
				pos = getLeftIndex(arr, element, mid + 1, high);
				return pos;
			}
			if (arr[mid] > element) {
				pos = getLeftIndex(arr, element, low, mid - 1);
				return pos;
			}
			if (arr[mid] == element) {
				pos = getLeftIndex(arr, element, low, mid - 1);
				if (pos == -1) {
					pos = mid;
				}
				return pos;
			}
		}
		return -1;
	}

	private int getRightIndex(int[] arr, int element, int low, int high) {
		int pos = 0;
		if (high >= low) {
			int mid = (low + high) / 2;
			if (arr[mid] < element) {
				pos = getRightIndex(arr, element, mid + 1, high);
				return pos;
			}
			if (arr[mid] > element) {
				pos = getRightIndex(arr, element, low, mid - 1);
				return pos;
			}
			if (arr[mid] == element) {
				pos = getRightIndex(arr, element, mid + 1, high);
				if (pos == -1) {
					pos = mid;
				}
				return pos;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		NumberOfOccurences numOccurences = new NumberOfOccurences();
		int[] arr = { 1, 2, 3, 3, 3, 4, 8, 9, 10, 20 };
		numOccurences.findNumOfOccurences(arr, 4);
		System.out.println("---------------");
		numOccurences.findNumOfOccurences(arr, 3);
	}
}

Output
----------
Element : 4
Left Index : 5
No of occurences : 1
---------------
Element : 3
Left Index : 2
Right Index : 4
No of occurences : 3

public class countOcc
{
public static void main(String []args)
{
int []arr={1,1,1,2,2,2,2,2,2,2,2,3,3,4,5,5,6,6,7,8,9,10,10,10,10,11};
for( int i=0;i<12;i++)
	System.out.println("The occurance of "+i+" is: "+cntOcc(arr,i,0,arr.length)); 
}
public static int cntOcc(int []data,int key,int low,int high)
{
int temp,mid,lcount=0,rcount=0;
if(low>high) return 0;
mid=(low+high)/2;
if(data[mid]==key)
	{	
	if((mid-1)>0)
		lcount=cntOcc(data,key,low,mid-1);
	if((mid+1)<data.length)
		rcount=cntOcc(data,key,mid+1,high);
	return (lcount+rcount+1);
	}
else if(data[mid]>key)
	{
	return cntOcc(data,key,low,mid-1);
	}
else 	{
	return cntOcc(data,key,mid+1,high);
	}
}

}

suppose that all the numbers are the same.
then the complexity is at least o(n), not o(log n)