find a number

[murali@pune]

Hi,

I have an array of 1001 integers. The integers are in random order, but

I know each of the integers is between 1 and 1000 (inclusive). In
addition, each number appears only once in the array, except for one
number, which occurs twice. Assume that I can access each element of
the array only once.


Here I need an algorithm to find the repeated number. If I used
auxiliary storage in my algorithm, can you find an algorithm that does
not require it?

 

[Thomas Weidenfeller]

I have an array of 1001 integers. The integers are in random order, but

I know each of the integers is between 1 and 1000 (inclusive). In
addition, each number appears only once in the array, except for one
number, which occurs twice. Assume that I can access each element of
the array only once.


Here I need an algorithm to find the repeated number. If I used
auxiliary storage in my algorithm, can you find an algorithm that does
not require it?

Nice homework question. How fare did you come with your algorithm?

/Thomas

 

[Niels Dybdahl]

Hi,

I have an array of 1001 integers. The integers are in random order, but

I know each of the integers is between 1 and 1000 (inclusive). In
addition, each number appears only once in the array, except for one
number, which occurs twice. Assume that I can access each element of
the array only once.


Here I need an algorithm to find the repeated number. If I used
auxiliary storage in my algorithm, can you find an algorithm that does
not require it?

Yes I can find an algorithm if I only need to find the value of the repeated
number and not the two positions.

Niels Dybdahl

 

[murali@pune]

yes I want to find only repeated number.

 

[opalpa]

Thomas suggested this is homework. I believe there is a good chance no
one will solve the entire problem as long as they believe this question
is homework.

Have fun

Opalinski
(e-mail address removed)
http://www.geocities.com/opalpaweb/

 

[Patricia Shanahan]

Hi,

I have an array of 1001 integers. The integers are in random order, but

I know each of the integers is between 1 and 1000 (inclusive). In
addition, each number appears only once in the array, except for one
number, which occurs twice. Assume that I can access each element of
the array only once.


Here I need an algorithm to find the repeated number. If I used
auxiliary storage in my algorithm, can you find an algorithm that does
not require it?

I can. The first solution that popped into my head needed auxiliary
storage. The second one did not.

What lines of thought are you following in working on this? Do you have
the auxiliary storage solution? Remember you are being given a lot of
data about the numbers in the input array. Try playing with those facts
a bit.

Patricia

 

[murali@pune]

every one knows but not interest to post answer. ?

 

[Timbo]

every one knows but not interest to post answer. ?

Everyone knows but are not interested to do your homework for you.

 

[TechBookReport]

every one knows but not interest to post answer. ?

No one wants to answer your homework. Where is your algorithm? Do you
have any code? Have you done any work other than to ask on this newsgroup?

 

[opalpa]

every one knows but not interest to post answer. ?

At least some people know. And yes, none of those who know are
interested in posting the answer. There is speculation that you are
looking for a homework solution. I'm pleased that people are not
providing a solution.

So how about you start playing along with the assistance you are
getting and answer Thomas' "How fare did you come with your algorithm?"
and Patricia's "What lines of thought are you following in working on
this? Do you have the auxiliary storage solution?"

Isn't this a homework question? And didn't you sign up willingly for
the class where it was assigned?

Regards,
Opalinski
(e-mail address removed)
http://www.geocities.com/opalpaweb/

 

[Thomas Schodt]

Hi,

I have an array of 1001 integers. The integers are in random order, but

I know each of the integers is between 1 and 1000 (inclusive). In
addition, each number appears only once in the array, except for one
number, which occurs twice. Assume that I can access each element of
the array only once.


Here I need an algorithm to find the repeated number. If I used
auxiliary storage in my algorithm, can you find an algorithm that does
not require it?

Yes, it is not difficult.

This is the test harness I used (no spoiler).

<code>
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public final class Duplicate {
private static final boolean DEBUG = false;
public static final int[] populateArray(int limit) {
int[] vi = new int[limit+1];
Integer[] va = new Integer[limit+1];
for(int i=1;i<=limit;++i) {
va = new Integer(i);
}
va[0] = new Integer(1 + (new Random().nextInt(limit)));
System.out.println(va[0]);
List l = Arrays.asList(va);
Collections.shuffle(l);
va = (Integer[])(l.toArray());
for(int i=0;i<va.length;++i) {
vi = va.intValue();
}
return vi;
}
public static final int findDuplicate(int[] vi) {

// this is where your code goes

}
public static final void main(String[] arg) {
int limit = Integer.parseInt(arg[0]);
int[] va = populateArray(limit);
System.out.println( findDuplicate(va));
}
}
</code>

 

[Patricia Shanahan]

every one knows but not interest to post answer. ?

That's right. The fact that we can find a solution should reassure you
that there is a solution out there - you just have to find it.

This looks like a homework problem. It appears to me that homework has
two purposes:

1. Give the student practice at the task.

2. Evaluate what the student can do.

Having us post the solution won't give you much practice. The fact that
this newsgroup includes many people who can solve the problem would
probably not surprise your instructor, but gives no information at all
about what you can do.

If it is not homework, please explain the application. How do you know
there is exactly one repeat and no omissions?

Patricia

 

[Chris Uppal]

I can. The first solution that popped into my head needed auxiliary
storage. The second one did not.

Oddly, I couldn't think of a solution until I read that[*]. I needed the extra
information that there /was/ an obvious solution before I could see the obvious
solution...

-- chris

([*] I'd got "stuck" on a completely different approach -- one that wouldn't
have solved the OP's problem anyway, but if I can find a problem that it /does/
solve elegantly, then I'll post it ;-)

 

[Patricia Shanahan]

No one wants to answer your homework. Where is your algorithm? Do you
have any code? Have you done any work other than to ask on this newsgroup?

Yes, he has done additional work. He has also posted this question to
comp.programming, and posted other homework-like questions to newsgroups
where people with algorithm skills might be found.

The next newsgroup I read after this one was comp.theory, where he wants
to know "how to write a recursive function program for generating all
possible permutations of a set of symbols".

Patricia

 

[Chris Uppal]

No one wants to answer your homework. Where is your algorithm? Do you
have any code? Have you done any work other than to ask on this
newsgroup?

Yes, he has done additional work. He has also posted this question to [...]

<grin>

The permutations one also went to comp.programming. For some reason we haven't
been blessed with that one here (yet).

To be fair, though, it does seem that the bulk of his postings have been
perfectly legitimate questions.

-- chris

 

[Roedy Green]

Here I need an algorithm to find the repeated number. If I used
auxiliary storage in my algorithm, can you find an algorithm that does
not require it?

The classic solution is to sort and scan for the dup, but of course
sorts require some aux storage.

A flat footed solution would be to scan for the first number, starting
at the second position then scan for the second starting at the third
etc.

Another even worse flat footed solution would be to scan for 0 then
when you find it set it to -1. Then scan for 1 and set it to -1. When
you are done scan for anything that is not -1.

 

[Roedy Green]

No one wants to answer your homework.

In that is because they have your best interests at heart. See
http://mindprod.com/jgloss/homework.html

 

[Roedy Green]

This looks like a homework problem. It appears to me that homework has
two purposes:

1. Give the student practice at the task.

2. Evaluate what the student can do.

It is either a homework problem or an artificial problem concocted to
teach programming. In either case, it does you no good if someone
else hands you the solution. It is like Oprah paying someone to ride
an exercise bike for her.

 

[alexandre_paterson]

I can. The first solution that popped into my head needed auxiliary
storage. The second one did not.

Hi,

the solution without extra storage that I've got involve accessing each
and every element in the array (only once, as stated in the problem).

Hower using extra-storage (like, say, 1000 bits) the search could
usually stop way before reaching the end.

Is your solution without extra-storage similar (in that it needs to
access every element)?

Bye, Alex

 

[Jussi Piitulainen]

The classic solution is to sort and scan for the dup, but of course
sorts require some aux storage.

Not all sorts do, but I don't think there is any way to sort the array
while accessing each element only once. That was required. (Making a
copy and accessing its elements many times is just cheating.)

The key here is that the elements are (1) small numbers, (2) all but
one of which are known. Numbers, so that we can do number things with
them. Small, so that we don't need to tell the student about arbitrary
precision arithmetic yet.

And it suffices that the known numbers are known; they need not
actually be unique or consecutive, nor need the odd one out be a
duplicate: we could have a 1000-int array and another 1001-int array
that contains the same numbers plus one other, in some order, and we
could find the extra number with essentially the same algorithm in one
pass.