i dont know O(n) but here is an O(nlgn) algorithm
reverse the second half, the final sequence obtained will be a bitonic
sequence
to sort a bitonic sequence
compare i with i+n/2,put smaller in first half and larger in other
finally you will get 2 bitonic sequences, 0->n/2 ans n/2+1 ->n
so do recu
Given an integer array of which both first half and second half are
sorted. Write a function to merge the two parts to create one single
sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to:
[-5,-2,1,3,3,6,8,8]
i have thought of t
dont multiply by 5! and 3! because sub-arrays have to remain sorted too so
there will be only ONE possible arrangement of 5 elements and 3 elements in
sub-array.
On Wed, Oct 13, 2010 at 9:27 AM, sudheer babu wrote:
> 8C5*(5!*3!)=8!
>
>
> On Tue, Oct 12, 2010 at 9:31 PM, ANUJ KUMAR wrote:
>
>> 56
8C5*(5!*3!)=8!
On Tue, Oct 12, 2010 at 9:31 PM, ANUJ KUMAR wrote:
> 56
>
> On Tue, Oct 12, 2010 at 5:09 PM, divya wrote:
> > Given a sorted array A with 8 integers.We want to have 2 sorted arrays
> > B(with 5 integers)
> > And C(with 3 integers) such that merging B and C would result in A.
> >
56
On Tue, Oct 12, 2010 at 5:09 PM, divya wrote:
> Given a sorted array A with 8 integers.We want to have 2 sorted arrays
> B(with 5 integers)
> And C(with 3 integers) such that merging B and C would result in A.
> How many such pairs exists
>
> --
> You received this message because you are subs
8C5 (8!/(3! * 5!))
On Tue, Oct 12, 2010 at 5:09 PM, divya wrote:
> Given a sorted array A with 8 integers.We want to have 2 sorted arrays
> B(with 5 integers)
> And C(with 3 integers) such that merging B and C would result in A.
> How many such pairs exists
>
> --
> You received this message bec
Given a sorted array A with 8 integers.We want to have 2 sorted arrays
B(with 5 integers)
And C(with 3 integers) such that merging B and C would result in A.
How many such pairs exists
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post t
hi,
this is regarding a problem from programming pearls by jon bentley
column 5.
I have few questions ,
1) how to check if an array is sorted or not. Can it be done it sub -
linear time
2) In section 5.8 problem 5, he describes saying that checking a array
is sorted or not takes n-1 operatio
