@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>
> > .
> > 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
