wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> CS: Repeated Number solution (in perl)
        
(Message started by: cmdrdran on Jul 24^th, 2002, 2:52am)

Title: CS: Repeated Number solution (in perl)
Post by cmdrdran on Jul 24^th, 2002, 2:52am

Not exactly elegant,
It works...

##########################################
#!/usr/bin/perl

my $num_string = <STDIN>;
chomp $num_string;
@all_seq = split(/ /, $num_string);
print "\n";
&find_it();

sub find_it {

$looking_for = shift(@all_seq) or return 0;
foreach $other_num (@all_seq) {
if ($looking_for == $other_num) {
print STDOUT "Hey, your repeating number is ${looking_for}\n.";
exit;
}
}
&find_it();
return 0;
}

print "There wasn't a repeating number there! look!\n";
print $num_string, "\n";
exit;
##########################################

Title: Re: CS: Repeated Number solution (in perl)
Post by ChOas on Jul 25^th, 2002, 3:34am

Maybe a bit more elegant:

#!/usr/bin/perl -w

use strict;

my @Input=split / /,<STDIN>;
for ($_=0;$_<@Input-1;++$_)
{
print "Repeat: $Input[$_]\n" if ($Input[$_]==$Input[$_+1]);
};

Title: Re: CS: Repeated Number solution (in perl)
Post by srowen on Jul 27^th, 2002, 12:25pm

How about more abstract solutions instead of perl implementations? It's not clear what the memory (or time) efficiency of these are.

Also, the problem isn't explicit on the following points which I believe we must assume to make this meaningful:
1) It is a sequence of n numbers
2) The sequence is not necessarily in sorted order

Otherwise the problem is entirely trivial.

There are three approaches I can think of:
1)
Brute force - look for the first number in the rest of the list, then the second, etc. O(n^2) time though!
2)
Sort the list and look for an adjacent pair of duplicates. Slow (O(nlogn)) but uses no additional storage.
3)
Add all the numbers. The sum of the numbers from 1 to n-1 is (n-1)*n/2. The calculated sum will exceed this value by the value of the repeated number. I think it's safe to call this "constant memory" unless n is very large. It's also O(n).

If there are two repeated numbers, 1) and 2) still work, but 3) doesn't.

Title: Re: CS: Repeated Number solution (in perl)
Post by -D- on Jul 27^th, 2002, 12:49pm

The answer to this problem is rather simple. You loop through each element in the array. And at every element you search each element beyond that for a matching element. If you detect one then print "match", mark a flag and exit the loop. The only thing you need to keep track of memory wise is the indexes and a boolean field to determine if a match was found or not. At the end of the process if no match was found (indicated by the flag), print that message.

The solution works for multiple repeated numbers if you remove the exit-the-loop requirement but has one downfall. If there were 3 of a number, it would print out a match twice.

This isn't very good since we're just looking for repeats. So, a better solution for this scenario is: Iterate through every element in the array, at each element search every element in the array starting from the FIRST element until a match is found. If a match is found and the index of the match is GREATER than the current iteration index, print out a match message. Without the GREATER construct, this would print out each pair twice or worse if triples existed. The problem still is that if triples existed, the second value would report a match with the third value. So, to resolve this, if the index of the match is LESS than the current index, you abort this iteration.

Lastly, if you wanted to know how many of an element there were, you would just keep a counter for each match, and the end of the inner loop if the counter was > 0, print out the match message and reset it.

The constant memory requirement is almost not a threat. A more interesting problem though would be, how do you do this in better than O(n²) time.
-D-

Title: Re: CS: Repeated Number solution (in perl)
Post by srowen on Jul 27^th, 2002, 12:57pm

See above for faster possibilities. Also, I think the problem is asking about two repeated numbers, not one number repeated twice (a triple).

Title: Re: CS: Repeated Number solution (in perl)
Post by -D- on Jul 27^th, 2002, 1:02pm

Ah, I didn't read clearly what you had posted.

My solutions work for any number of repeated numbers repeated any number of times.

I built up from: finding one repeat, finding multiple numbers repeated once, finding multiple numbers repeated multiple times.

You're right to mention that people ought to post how their solutions meet the requirements, the code is trivial compared to the methods.
-D-

Title: Re: CS: Repeated Number solution (in perl)
Post by AJ on Aug 4^th, 2002, 7:35am

The fastest way to solve this would be to use bucket sort. Create an integer array of size n-1 initialized to zero. Start reading the numbers and and increase the value at index = number by one.
Of course this doen't satisfy the "constant memory" requirement, but its O(n) and would work for any number of numbers repeated any number of times ;)

Title: Re: CS: Repeated Number solution (in perl)
Post by william wu on Aug 8^th, 2002, 8:46pm

on 07/27/02 at 12:25:08, srowen wrote:

Also, the problem isn't explicit on the following points which I believe we must assume to make this meaningful:
1) It is a sequence of n numbers
2) The sequence is not necessarily in sorted order

Otherwise the problem is entirely trivial.

Thanks [srowen]; indeed it wasn't clear at all. It's nice to have such meticulous visitors. I have rephrased it now.

Title: Re: CS: Repeated Number solution
Post by zameericle on Aug 13^th, 2002, 2:49am

okay.. here's what I have to find multiple repeating numbers (1 or 2)

take the product of 1..n-1 = (n-1)! = m
take the product of the elements in the set = k

suppose S = {1 4 3 3 2 2 1}

in this case m = 24 (4.3.2.1), k = 144
divide k/m = 6

find all gcd of 6 between (1..n-1) = {3,2}

the elements in the gcd are the ones that are repeated.

Can anyone verify this?

thanks

Title: Re: CS: Repeated Number solution (in perl)
Post by TimMann on Aug 31^st, 2002, 6:37pm

Fast way to detect two repeated numbers x, y with constant memory: Sum the given numbers and subtract sum(1,..., n-1) = (n-1)*n/2, calling the result a. Take the product of the given numbers and divide by prod(1,..., n-1) = (n-1)!, calling the result b. Now solve the equations x+y=a, x*y=b.

Not going into details of the code, it's obvious this takes constant space and O(n) time, assuming addition and multiplication are constant time operations.

Title: Re: CS: Repeated Number solution (in perl)
Post by AlexH on Aug 31^st, 2002, 7:42pm

Computing n! is not constant memory because the number of bits needed to represent n! grows proportional to n log n. You could try to get around this by playing with logarithms (or better, modular arithmetic), but its not necessary since there is a simpler way. Let be S our set and T is the set {1,...,n-1}. If our 2 repeated values are x and y, then compute
A=sum_S(i) - sum_T(i) = x + y
B=sum_S(i²) - sum_T(i²) = x²+y²

Assuming my algebra was right, solving yields:
{x,y} = (A +/- sqrt(2B-A²))/2

Extend this to k repeated values by going to sums over the kth power.

Edited: Sigh, my algebra was right but my typing wasn't. Corrected the formula.