@atul...
if its the sum of the elements to the left of a[i] which are smaller the my
approach works w/o any flaw....
here's the working code for it....http://ideone.com/CH7VW
if its the sum of all elements lesser than the element a[i] then this algo
is surely wrong
n we then have to proceed by the avl trees or some height balanced tree n
the algo would be of TC-O(nlogn)
btw nyc catch thnx...
Regards,
PAYAL GUPTA
On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor <pkjee2...@gmail.com> wrote:
> 1)First map the array numbers into the position in which they would be, if
> they are sorted,for example
> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
> 2)Now for each number ,find the cumulative frequency of index ( = the
> corresponding number in the map - 1).
> 3)Output the cumulative frequency and increase the frequency at the
> position (=the corresponding number in the map) by the number itself.
> Example
> {3,5,1,6,7,8} Map of which would be {2,3,1,4,5,6}
> Process the numbers now,
> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
> so output 0
> Increase the frequency at index 2 to the number 3.
> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
> Increase the frequency at index 3 to the number 5.
> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at position
> 1 by 1.
> Similarly for others.
>
>
> --
> 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.
>
--
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.
