find a number

[Chris Uppal]

You just misread the OP's exercise, so basically we're both right.

Agreed. As I said in another post, I originally formulated this stuff in a
1-based language, and then translated everthing back by hand (which is why
there are typos in my "example"). I didn't notice that that changed the point
at which you should start following the chain.

It is an interesting question what the complexity is. This will be the
average length of a cycle. Intuitively, I'd say this is n/2. I don't
expect something sublinear here.

I think your intuition must be better than mine. Alexandre posted that the
algorithm had to check around 2/3 of the array (for the N=1000 case). I found
an analysis on the web:
http://www.inference.phy.cam.ac.uk/mackay/itila/cycles.pdf
which states that the average cycle length is:
N / ln(N)
and that the average length of a cycle /passing through a specifed point/ is:
(N+1) / 2
That's for pure permutations, of course. If we assume that in this case the
tail itself is probably as long as the average cycle passing through a
specified point, and that the cycle it joins onto is essentaily random, then
you'd expect to have to check the sum of the above array slots before the
search terminates. In the case where N=1000 that works out to about 650, so it
might not be too far off as an estimate. If that's true then it is O(N).

-- chris

 

[Piotr Kobzda]

You have to.

Ooops, you don't. I have had cycles in my mind what Chris pointed out
earlier. Now, after deeper analysis, I see my mistake.
Sorry for the confusion.


Regards,
piotr

 

[music]

int num;
int ctr;
int a[]=new int[1001];
int b[]=new int[100];
for(int i=0;i<1001;i++)
{
b=a;
//copying array a to array b
}
for(int i=0;i<1001;i++)
{
ctr=0;
num=a;
for(int j=0;j<1001;j++)
{
if(b[j]==num &&b[j]!=0)
{
ctr++;
b[j]=0;
}
if(ctr==2)
{
System.out.println("the no. is"+num);
break;}
}

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

music schreef:

int num;
int ctr;
int a[]=new int[1001];
int b[]=new int[100];

1001, I suppose.

for(int i=0;i<1001;i++)
{
b=a;
//copying array a to array b
}

System.arrayCopy(a, 0, b, 0);

for(int i=0;i<1001;i++)
{
ctr=0;
num=a;
for(int j=0;j<1001;j++)
{
if(b[j]==num &&b[j]!=0)
{
ctr++;
b[j]=0;
}
if(ctr==2)
{
System.out.println("the no. is"+num);
break;}
}

This uses O(n) auxiliary memory, and O(n³) time. Not really the optimal
solution we've been searching for.

H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEJ7Tze+7xMGD3itQRAh9fAJ9ULe9O6j3fIFPsadY5fqHXrKpOiwCeI7Bo
NpjrZS25+XPtF6wwyhjK02M=
=1yOQ
-----END PGP SIGNATURE-----

 

[Don Roby]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

music schreef:

int num;
int ctr;
int a[]=new int[1001];
int b[]=new int[100];

1001, I suppose.

for(int i=0;i<1001;i++)
{
b=a;
//copying array a to array b
}

System.arrayCopy(a, 0, b, 0);

for(int i=0;i<1001;i++)
{
ctr=0;
num=a;
for(int j=0;j<1001;j++)
{
if(b[j]==num &&b[j]!=0)
{
ctr++;
b[j]=0;
}
if(ctr==2)
{
System.out.println("the no. is"+num);
break;}
}

This uses O(n) auxiliary memory, and O(n³) time. Not really the optimal
solution we've been searching for.

H.

Indeed. I suspect a pure arithmetic trick is pretty near optimal,
passing through the entire array once, and needing one collecting
variable for the result. O(n) and minimal auxiliary.

Compute the difference between the sum of the values and the sum of the
indices.

This depends heavily on the specifics of a[] containing all the numbers
except 0 and exactly one twice. The cycle-chasing solution discussed in
this thread is more fun though, and more apt to generalize usefully.

Hope the OP already turned in his homework. Just in case, I opted to
describe the computation instead of posting code, so he at least has to
translate.

 

[Jussi Piitulainen]

Compute the difference between the sum of the values and the sum of
the indices.

This depends heavily on the specifics of a[] containing all the
numbers except 0 and exactly one twice.

The content of the array does not matter as long as we know the sum
without the additional number, and can add the numbers without blowing
any limits. The additional number need not be a duplicate, either; any
old number will do.

The cycle-chasing solution
discussed in this thread is more fun though, and more apt to
generalize usefully.

At least some of the solutions discussed will overwrite the array.
This was not in the specification of the problem.

 

[Chris Uppal]

Out of curiosity, I ran a few million random simulation with
Hendrik's code and, for an array of 1000 elements, and it
took on average 667 reads in the array.

(Very quick follow-up)

FWIW, it seems to take approx 2/3 * N array reads whatever the size of the
array. I have no idea why.

-- chris

 

[Niels Dybdahl]

(Very quick follow-up)

FWIW, it seems to take approx 2/3 * N array reads whatever the size of the
array. I have no idea why.

The two identical numbers are placed at random places in the sequence. You
will not find them until you have iterated through to both places, so if the
places are i and j, then you have to read max(i, j) times from the array.
When i and j are random within a range then the average value of max(i,j)
apparently is 2/3 of the range.

Niels Dybdahl

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Don Roby schreef:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

music schreef:

int num;
int ctr;
int a[]=new int[1001];
int b[]=new int[100];

1001, I suppose.

for(int i=0;i<1001;i++)
{
b=a;
//copying array a to array b
}

System.arrayCopy(a, 0, b, 0);

for(int i=0;i<1001;i++)
{
ctr=0;
num=a;
for(int j=0;j<1001;j++)
{
if(b[j]==num &&b[j]!=0)
{
ctr++;
b[j]=0;
}
if(ctr==2)
{
System.out.println("the no. is"+num);
break;}
}

This uses O(n) auxiliary memory, and O(n³) time. Not really the optimal
solution we've been searching for.

H.

Indeed. I suspect a pure arithmetic trick is pretty near optimal,
passing through the entire array once, and needing one collecting
variable for the result. O(n) and minimal auxiliary.

Compute the difference between the sum of the values and the sum of the
indices.

This depends heavily on the specifics of a[] containing all the numbers
except 0 and exactly one twice. The cycle-chasing solution discussed in
this thread is more fun though, and more apt to generalize usefully.

Somewhere else in the thread you find a solution that will work in 2/3n,
(as Niels Dybdahl astutely pointed out) which is still O(n), of course,
but generally faster then this, which has constant factor 1.
It also relies on the numbers being in the array, and modifies it.

Hope the OP already turned in his homework. Just in case, I opted to
describe the computation instead of posting code, so he at least has to
translate.

Good point. I hope I waited long enough before posting my solution...

H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEKPY4e+7xMGD3itQRAu1GAJsFYV50QnnPLfb06UyAfnOxxBNFqQCfaQTu
JVFEkBARRwyBDnLU+RzlTfk=
=2NuH
-----END PGP SIGNATURE-----

 

[Chris Uppal]

The two identical numbers are placed at random places in the sequence. You
will not find them until you have iterated through to both places, so if
the places are i and j, then you have to read max(i, j) times from the
array. When i and j are random within a range then the average value of
max(i,j) apparently is 2/3 of the range.

A nice argument. Thanks !

-- chris