Replying to myself, I think the pseudocode algorithm I posted earlier
is wrong. Here is the correction:
for i = 1 to n
j = a(i)
while a(j) not_equal j
k = 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
As before, the algorithm is O(n) in time and O(1) in space. Also note
that the algorithm will detect any number of missing numbers in the
range 1 to n in an array of size n, not just two missing numbers.
Dave
On Oct 12, 1:19 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>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
>
> > - Show quoted text -- 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.
