Algorithm to find the intersection of two or more songs

Question

Lets say we have a bunch of radios and each radio plays the same song on a loop over and over again. Is it possible to synchronize all the songs from all the radios? Can we find a time where we hear all the songs from the beginning?

For the sake of simplicity we will say that we only have two radios.

I have the following formulas :

c and z represent the length of the song in seconds. a and x represent the current position in the song ( in seconds ) S represents the time when C and Z synchronize. ( When both songs start at the same time )

For example :

Song 1
a = 17 : the time before the song ends.
b = 8 : the rest of the song.
c = a + b which is the full song in seconds.
And
Song 2 
x = 8 : the time before the song ends.
y = 9 : the rest of the song.
z = 8 + 9 which is the full song in seconds.

Song 1 : a + ( a + b) => S
Song 2 : x +(( x + y ) × n) => S

Song 1 : 17 + ( 17 + 8) => 42
Song 2 : 8 + ((8 + 9)) = 25
So in order to synchronize song 2 with song 1 we have to multiply (x + y)    
by two and add x to it.

Song 2 : 8 + ((8 + 9) x 2) => 42

So S = 42 and so the two songs will synchronize after 42 seconds.

Now This first example is the simplest one. For the other cases i would have to multiply z and c by more than two in order to get the appropriate S for them.

I have some other inputs , and i've tried to come up with an algorithm that will return S for me , but i had no luck with that.

Here is what i came up with so far :

c = a + b
a = 16
b = 4
c = 20
s = 216

And

z = x + y
x = 12
y = 5
z = 17
s = 216
S is the LCM of c and z

In the first example S was found this way :

s = x +(z × n)
n = ( s − x ) ÷ b
12 + ( 17 × 12) = 216

and

s = a + (c × n)
n = ( s − a ) ÷ b
16 + ( 20 × 10 ) = 216

I came up with the two formulas below Based on the value of S. But i need to figure out a way to find n without actually using S. Or in other words i need to figure out a way to find how many times i should multiply ( a + b) by n and ( x + y) by n to get S.

n = ( s − a ) ÷ b
S = x + ( y × n)

But These formulas obviously won't work as they require S. And we can't use that because that should be the result of the formula that i am trying to come up with.

Here are other examples for some calculations :

a2 = 52
b2 = 4
c2 = 56
s2 = 276

x2 = 60
y2 = 12
z2 = 72
s2 = 276

Here is a situation where it will never be Synchronized :

A1 = 14
B1 = 4
C1 = 18
S1 = Never synchronizes

A2 = 19
B2 = 5
C2 = 24
S2 = Never synchronizes

And Here are some situation where the songs are already Synchronized :

Case 1

A2 = 17  
B2 = 0 
C2 = 17 
S4 = 0

A3 = 25  
B3 = 0 
C4 = 25  
S4 = 0

Case 2

A4 = 0 
B4 =  13  
C4 = 13  
S4 = 0


A5 = 0 
B5 = 21 
C5 = 21  
S5 = 0

I was thinking about using the Least Common Multiple but i am not sure how to implement it in this situation or if its the right solution for this problem.

The Algorithm i want to come up with should also work if there are more than 2 songs. For example finding S for 3 or 4 songs.

The main problem with this Algorithm is deciding wether the two songs Synchronize or not , The calculation itself is not that hard. Can you help me please ? Thanks in advance

Answer 1

The least common multiple of c and z is the interval between consecutive times that the songs synchronize (if they synchronize at all). This means that, if we can determine one time, we can find the rest by adding (or subtracting) a multiple of the LCM. To find this time (and indeed, the LCM), use the extended Euclidean algorithm to find integers T, U that satisfy the equation

 (c - a) + T*c = (z - x) + U*z

which is equivalent under the substitution V = -U to

 T*c + V*z = (c - a) - (z - x).

In detail, find the GCD of c and z, check that it divides (c - a) - (z - x), then multiply the Bézout coefficients through by ((c - a) - (z - x))/GCD(c, z).

Answer 2

I have written this code with the logic i have mentioned in comments. Basic idea is to find integers n1 and n2 such that (n1*c)-(n2*z)=(x-a)

Brief explanation about how I arrived at this equation:

s1 = a+(n1*c)

s2 = x+(n2*z)

We need s1=s2

=> a+(n1*c) = x+(n2*z)

=> (n1*c)-(n2*z) = (x-a)

We need to find n1 and n2 which satisfies the above equation. The solution exists if and only if GCD of c and z divides (x-a).

Please note: This logic works for two stations.

Here is my code.

#include <stdio.h>

void findVal(unsigned int a, unsigned int c, unsigned int x, unsigned int z) ;
unsigned int getGCD(unsigned int n1, unsigned int n2);

int main()
{
    findVal(2, 37, 3, 43);
    return 0;
}

void findVal(unsigned int a, unsigned int c, unsigned int x, unsigned int z) {

    unsigned int  n1       = 0;
    unsigned int  n2       = 0;
    unsigned char foundVal = 1;
    unsigned int  s1       = a;
    unsigned int  s2       = x;

    //No need to find n1 and n2 if songs are already at the starting point.
    if((a == c) && (x == z))
    {
        s1 = 0;
        s2 = 0;
    }

    //No need to find n1 and n2 if remaining times are same.
    else if(a != x)
    {
       //Remaining times are not same.
       foundVal = 0;

       //Find GCD of c and z.
       unsigned int gcd = getGCD(c, z);

        //There is a solution only if the difference of x and a is divisible by the gcd.
       if(0 == (x-a) % gcd)
       {
           for(n2=1; n2<(unsigned int)-1; n2++)
           {
               unsigned int temp1 = (z*n2)+(x-a);
               if(0 == temp1%c)
               {
                    n1 = temp1/c;
                    s1 = a + n1*c;
                    s2 = x + n2*z;

                    foundVal = 1;
                    break;
               }
           }
       }
    }

    if(1 == foundVal)
    {
        printf("Found n1[%u] n2[%u] s1[%u] s2[%u]\n", n1, n2, s1, s2);
    }
    else
    {
        printf("Could not find n1 and n2\n");
    }
}

unsigned int getGCD(unsigned int n1, unsigned int n2)
{
    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("GCD = %u\n",n1);

    return n1;
}

Output:

Found n1[21] n2[18] s1[793] s2[793]