You don't really need a program. Only one number, 9, can be added to 16 to make a perfect square, so 16 must be at one end of the list. Through a sequence of forced choices, you can build the list 16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3. At this point, you can choose either 1 or 6. Trying 1, you can choose either 8 of 15. 8 leads to a dead end -- no unused number can add to 8 giving a perfect square. 15 leads to the continuation 15, 10, 6, but then the only remaining number, 8, doesn't work. Reverting to choosing 6 instead of 1, the sequence continues 6, 10, 15, 1, 8.
Thus, the sequence is 16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8. Or its reverse. If you insist on a program, I suppose you could write that sequence in a print statement and give an O(1) solution. Dave On Sep 13, 3: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.
