On Tue, Oct 12, 2010 at 9:04 PM, vijay k <[email protected]> wrote: > @Nikhil, > > But your solution changes original array, which is not an acceptable > method. > Ya I know.But he didnt explicitly mention that.If we can't change the original array then this is not an acceptable algorithm.
> > On Tue, Oct 12, 2010 at 6:18 PM, Nikhil Agarwal <[email protected] > > 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> >>> 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 [email protected]. >>> > > To unsubscribe from this group, send email to >>> > > [email protected]<algogeeks%[email protected]> >>> <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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [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.
