CODEWITHSUNDEEP
c++algorithm
user697417
user697417

Reputation: 69

algorithm: find count of numbers within a given range

given an unsorted number array where there can be duplicates, pre-process the array so that to find the count of numbers within a given range, the time is O(1).

For example, 7,2,3,2,4,1,4,6. The count of numbers both >= 2 and <= 5 is 5. (2,2,3,4,4).

Upvotes: 5

Views: 5278

Answers (4)

Rajesh Ugemuge
Rajesh Ugemuge

Reputation: 1

int main()
{   
    int arr[8]={7,2,3,2,4,1,4,6};
    int count[9];
    int total=0;    

    memset(count,0, sizeof(count));

    for(int i=0;i<8;i++)
        count[arr[i]]++;

    for(int k=0;k<9;k++)
    {
        if(k>=2 && k<=5 && count[k]>0 )
        {
            total= total+count[k] ;     
        }
    }

    printf("%d:",total);
    return 0;
}

Upvotes: 0

rajya vardhan
rajya vardhan

Reputation: 1131

Since we need to access in O(1), the data structure needed would be memory-intensive.
With Hash Table, in worst case access would take O(n)

My Solution:
Build a 2D matrix.
array = {2,3,2,4,1,4,6} Range of numbers = 0 to 6 so n = 7
So we've to create nxn matrix.
array[i][i] represents total count of element = i
so array[4][4] = 2 (since 4 appears 2 times in array)
array[5][5] = 0
array[5][2] = count of numbers both >= 2 and <= 5 = 5 

//preprocessing stage 1: Would populate a[i][i] with total count of element = i
a[n][n]={0};
for(i=0;i<=n;i++){
  a[i][i]++;
}

//stage 2
for(i=1;i<=n;i++)
  for(j=0;j<i;j++)
     a[i][j] = a[i-1][j] + a[i][i];
//we are just adding count of element=i to each value in i-1th row and we get ith row.

Now (5,2) would query for a[5][2] and would give answer in O(1)

Upvotes: 1

jkerian
jkerian

Reputation: 17066

This sounds suspiciously like one of those clever interview questions some interviewers like to ask, which is usually associated with hints along the way to see how you think.

Regardless... one possible way of implementing this is to make a list of the counts of numbers equal to or less than the list index.

For example, from your list above, generate the list: 0, 1, 3, 4, 6, 6, 7, 8. Then you can count the numbers between 2 and 5 by subtracting list[1] from list[5].

Upvotes: 3

Jerry Coffin
Jerry Coffin

Reputation: 490808

Sort the array. For each element in the sorted array, insert that element into a hash table, with the value of the element as the key, and its position in the array as the associated value. Any values that are skipped, you'll need to insert as well.

To find the number of items in a range, look up the position of the value at each end of the range in the hash table, and subtract the lower from the upper to find the size of the range.

Upvotes: 5

Related Questions