CODEWITHSUNDEEP
algorithm
Smorts
Smorts

Reputation: 95

Algorithm - find the longest string

On exam I had to write the algorithm that would give the answer to that question:

"In numbers.txt file there are 500 numbers separated by new lines. Find the longest string of numbers whose largest common divisor is greater than one. In other words, there exists a number that is a divisor of them all. As an answer give a value of the first number in the string, the length of the string and the number which is GCD of them all."

My first idea was soo not optimal. I didn't write it but conception is something that looks like that:

int numbers[500]; // array for numbers

ofstream allstrings;
allstrings.open("allstrings.txt");

int max; // lets say that i know what is max number

for(int i=2; i<x; i++)
{
    string found_string ="";
    for(int j=0; j<500; j++)
    {

        // looking for all strings whose common divisor is i
        if(foundstring)
        {
        allstrings << found_string << endl;
        found_string = "";
        }
    }

}

After that i would just find the longest string.

To be honest at the moment I don't have any better idea. I would be gratefull for any help :)

Upvotes: 2

Views: 350

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

With 500 numbers you can simply brute force this with O(n^2) gcd computations.

For each starting point try increasing the length of the string until the gcd becomes equal to 1.

Note that gcd(a,b,c) is equal to gcd(gcd(a,b),c) so you only need 1 extra gcd computation for each iteration of the loop.

Example Python Code

A=[3,7,21,6,9,10]

from fractions import gcd
best = ''
for start,g in enumerate(A):
    length = 1
    for x in A[start:]:
        g = gcd(g,x)
        if g==1:
            break
        if length>len(best):
            best = A[start:start+length]
        length += 1
print best

this prints:

[21, 6, 9]

Upvotes: 3

kmichael08
kmichael08

Reputation: 81

If complexity matters, you can try factorizing your numbers first. Then for each prime number divisor of the previous number, try to 'prolong' the sequence. If numbers share some common divisor, the share a common divisor being a prime number, in particular. Moreover, the number of different prime divisors is quite small :

http://math.stackexchange.com/questions/409675/number-of-distinct-prime-factors-omegan

In other words, algorithm is dynamic. Keep the list of values (prime divisor, max_length). If the next number is divisible by p, then increase max_length of p, otherwise set it to 1. Easy factorization is at square root time or maybe you can use Euclidean sieve first.

Upvotes: 0

Related Questions