@Nikhil, But your solution changes original array, which is not an acceptable method.
On Tue, Oct 12, 2010 at 6:18 PM, Nikhil Agarwal <nikhil.bhoja...@gmail.com>wrote: > @Asquare : Please check the following example: > > Given: an array of numbers ranging from 1-n > A[]= 3,3,5,2,1,2 > > As we encounter a number make the index of that number negative if it is > positive. > > A[]= -3,-2,-5,2,-1,2 > > Since our index 4 and 6 are positive after the complete pass we conclude > they are missing ones. > > Advantages: No extra space requirement & time is O(n). > > > On Tue, Oct 12, 2010 at 11:49 AM, Dave <dave_and_da...@juno.com> wrote: > >> @Asquare: The two numbers that are not present at least once must be >> missing. Suppose that a and b are missing and c and d occur twice >> (with the possibility that c = d so that one number occurs three >> times). We are going to need four equations in the four unknowns a, b, >> c, and d. Here are four possible equations: >> >> 1. The sum of the numbers = n(n+1)/2 - a - b + c + d, >> 2. The sum of the squares of the numbers = n(n+1)(2n+1)/6 - a^2 - b^2 >> + c^2 + d^2, >> 3. The sum of the cubes of the numbers = n^2(n+1)^2/4 - a^3 - b^3 + >> c^3 + d^3, and >> 4. The sum of the fourth powers of the numbers = n(n+1)(2n+1) >> (3n^2+3n-1)30 - a^3 - b^3 + c^3 + d^3. >> >> This system of equations probably will take some fancy algebra to >> solve for a, b, c, and d. >> >> If it is permitted to rearrange the array, another way to do this is >> as follows using 1-based arrays (warning: untested pseudocode) >> >> for i = 1 to n >> j = i >> while a(j) not_equal j >> k = a(a(j)) >> a(j) = j >> j = k >> end_while >> end_for >> for i = 1 to n >> if a(i) not_equal i >> print i " is missing" >> end_if >> end_for >> >> This puts each number in its own spot in the array. Obviously missing >> numbers can't be in their own spots. Because each number is moved only >> once, the algorithm is O(n). >> >> @Bharath. Of course, n! will overflow quite quickly, and two equations >> isn't enough to determine the two missing numbers, since there are two >> more unknowns. >> >> Dave >> >> On Oct 11, 8:11 pm, bharath kannan <bharathgo...@gmail.com> wrote: >> > sum of n elements from 1=n(n+1)/2 >> > product from 1 to n=n! >> > calculate dis.. >> > sum=calculated sum-orig sum >> > prod=calculated prod-orig prod >> > with dis form quadratic eq and solve... >> > hope this works... >> > >> > >> > >> > On Tue, Oct 12, 2010 at 12:29 AM, Asquare <anshika.sp...@gmail.com> >> wrote: >> > > Given an array of size n. It contains numbers in the range 1 to n. >> > > Each number is present at least once except for 2 numbers. >> > > Find the missing numbers. >> > >> > > I know of a solution using another array to store frequency of each >> > > number.. >> > > But this holds for than 2 nums also.. >> > > So Is there any other solution apart from this specific for 2 nums and >> > > of lesser complexity..?? >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To post to this group, send email to algoge...@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> <algogeeks%2bunsubscr...@googlegroups.com> >> > > . >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >> > >> > - Show quoted text - >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Thanks & Regards > Nikhil Agarwal > Senior Undergraduate > Computer Science & Engineering, > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
