Let's say we begin with an array that has numbers as so:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
The square that we'll be aiming for is 9,
break this array in 2 parts 1-8 9-16,
begin loop at left=1 right = len-1: left>right; left+=2, right-=2 //
len = 8 for each sub array
do:
swap( a[left], a[right]) // so swap (2, 8) (4, 6)
repeat for the other half (sum will be 25).
for each half you need 2 operations (swaps). O(log n) + O (log n).
Correct me if I'm wrong.
The reason I did it in 2 parts is because, a single array for sum of
consecutive elements to be 16, leaves 16 and 8 out.
I believe this would work for larger sequences too, the number of
partitions would be greater though.
On Sep 13, 1:53 pm, bittu <[email protected]> wrote:
> Write a program to arrange numbers from 1 to 16 such that the sum of
> two consecutive numbers is a perfect square
>
> in O(n) is solution possible in O(logn)
>
> Regards
> Shashank
--
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.
