heres a O(n) solution.. correct me if am wrong..
1. In order to get the count in O(1) we need to place the count of each
number in their respective index.So before storing the count we need to
swap the nos. in such a way that all k<=n are at their respective
index.This can be done in O(n)
int arr[]={1,2,1,0,4};
int sz=sizeof(arr)/sizeof(int);
int x,y;
for(int i=0;i<sz;i++)
{
while(arr[i]!=arr[arr[i]])
{
x=arr[i];
y=arr[arr[i]];
arr[i]=y;
arr[x]=x;
}
}
This will take O(n) time ...as for every loop we are setting one number to
its respective index and then moving to the next number.
2. Now set the count to -1 for all i..such that arr[i] equal to i.
for(int i=0;i<sz;i++)
{
if(arr[i]==i)
arr[i]=-1;
}
3. Now for all the numbers that are >0 ,we need to increment the count in
their respective index.And set their count =0 as there is no such number
for which arr[i]==i.
for(int i=0;i<sz;i++)
{
if(arr[i]>0)
{
arr[arr[i]]--;
arr[i]=0;
}
}
4.Now this array contains the count at their respective index.
int fun(int arr[],int x)
{
return -arr[x];
}
On Wed, Feb 15, 2012 at 10:48 PM, Dave <dave_and_da...@juno.com> wrote:
> @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 <tusharkanta.r...@gmail.com> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
