CODEWITHSUNDEEP
c
Timotius Satrio
Timotius Satrio

Reputation: 58

Making linear search more efficient

i have a problem of 3 light bulbs that turn on at different rate and were told to find and total the amount of when they turn on at the same time (based on given range of time). example: 1 2 3 1 20 (1 is starting time and 20 is end time) would output 36. (6 + 12 + 18). This code below works, but it could be faster. How can i make this better? Thank you for helping.

long long int total = 0, time1 = 0, time2 = 0, time3 = 0, start = 0, end = 0;

        scanf("%lli %lli %lli %lli %lli", &time1, &time2, &time3, &start, &end);
        
        for(int j = start; j <= end; j++)
        {  
            if(j % time1 == 0 && j % time2 == 0 && j % time3 == 0)
            {
                total = total + j;
            }
        }
        printf("Case #%i: %lli\n", testcase, total);

Upvotes: 0

Views: 79

Answers (2)

Ian Abbott
Ian Abbott

Reputation: 17403

The problem can be broken down to the following steps:

  1. Find the least common multiple, LCM of the turn-on times.
  2. Find the first and last occurrences of multiples of LCM within the desired range [start, end] by rounding start up to a multiple of LCM to get first, and by rounding down end to a multiple of LCM to get last.
  3. Find the number of multiples of LCM within the range [first, last], N = ((last - first) / LCM) + 1.
  4. Sum the multiples of the LCM within the range [first, last], sum by using the formula for the sum of an arithmetic progression, sum = (N * (first + last)) / 2.

The least common multiple, LCM of the turn-on times can be found by first finding the greatest common divisor, GCD of the turn-on times, and the product, P of the turn-on times, then LCM = P / GCD. The well-known Euclidean algorithm can be used to find the greatest common divisor of a pair of numbers, and this algorithm can be used multiple times to determine the overall greatest common divisor.

The above steps are implemented by the function get_total below.

unsigned long long int gcd(unsigned long long int a, unsigned long long int b)
{
    while (b) {
        unsigned long long int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

unsigned long long int
get_total(unsigned long long int start, unsigned long long int end,
        unsigned int ntimes, const unsigned long long int *times)
{
    unsigned long long int g;   /* GCD of times */
    unsigned long long int l;   /* LCM of times */
    unsigned long long int first, last;
    unsigned long long int n;
    unsigned long long int total;

    if (ntimes == 0 || times[0] == 0)
        return 0;   /* error */

    /* Calculate GCD and LCM of times. */
    g = times[0];
    l = 1;
    for (unsigned int i = 1; i < ntimes; i++) {
        if (times[i] == 0)
            return 0;   /* error */
        g = gcd(times[i], g);
        l *= times[i];
    }
    l *= times[0] / g;
    /* Get the first and last occurrences of multiples of LCM in range. */
    first = ((start + (l - 1)) / l) * l;    /* round up */
    last = end - (end % l);                 /* round down */
    if (first > last)
        return 0;
    /* Get number of occurrences of multiples of LCM in range. */
    n = ((last - first) / l) + 1;
    /* Get sum of arithmetic progression of multiples of LCM in range. */
    total = (n * (first + last)) / 2;
    return total;
}

ntimes is the number of light bulb turn-on times in the array pointed to by times.

Upvotes: 1

Aplet123
Aplet123

Reputation: 35512

Like many algorithmic problems, there's a mathematical observation that can greatly speed up your code. For the time to be divisible by all 3 lightbulbs, the time must be divisible by their least common multiple. Therefore, you get a regular interval that you have to check for between the start and the end. This can also be done with another formula.

Upvotes: 5

Related Questions