@Tushar: If we are going to use A[i] as an index into the array A[],
we must have 0 <= A[i] < N.
We can use a negative in A[i] to indicate that i occurs -A[i] times.
The code would look something like this:
//preprocessing...
int i, j, m;
for( i = 0 ; i < N, ++i )
{
j = A[i];
while( j >= 0 )
{
if( A[j] >= 0 )
{
m = A[j];
A[j] = -1;
j = m;
if( j <= i ) break;
}
else
{
A[j]--;
break;
}
}
}
Here is how this works: For each value of i, if A[i] < 0, we already
have processed it, so nothing more is required. Otherwise, suppose
that A[i] has the value j. Then if A[j] < 0 then we already have
processed at least one occurrence of j, so we just decrement A[j] to
indicate that an additional value j has occurred in A. But if A[j] >=
0, this is the first time j has occurred. We set the value of A[j] to
-1 to indicate that j has occurred once, but before we lose the value
of A[j], we have to process its value. This results in the while loop
to run through the chain of numbers until we get to an entry we
already have processed.
Prerocessing is O(N) because the statement A[j] = -1 in the while loop
can be executed at most k times and A[j]-- can be executed at most N-1
times during all iterations of the for loop. And since one of these is
executed on every iteration of the while loop, the while loop itself
can be executed no more than N+k-1 < 2*N times during all iterations
of the for loop.
//determining count of number of original A[i] == x...
count = A[x] < 0 ? -x : 0;
Dave
On Feb 14, 10:10 pm, TUSHAR <[email protected]> wrote:
> Given an array of size N having numbers in the range 0 to k where
> k<=N, preprocess the array inplace and in linear time in such a way
> that after preprocessing you should be able to return count of the
> input element in O(1).
>
> Please give some idea ........!!
> Thanks..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
