Need a faster algorithm to count if a product is smaller than a given number

Question

I have the next problem: My program reads two arrays and multiplies each element of the first array with each of the 2nd array. I have to count the number of results smaller than a given number. My code works correctly but i need to find a faster algorithm.

Here is my code:

void sort(int *array, int length)
{
    int index, jndex = 0, aux, compElPoz;
    for(index = 1; index < length; index++)
    {
        jndex = index - 1;
        compElPoz = index;
        while(array[compElPoz] < array[jndex])
        {
            aux = array[compElPoz];
            array[compElPoz] = array[jndex];
            array[jndex] = aux;
            if(jndex > 0)
                jndex--;
            compElPoz--;
        }
    }
}
int main()
{
    unsigned int n, in, jn, nr = 0, p, m;
    scanf("%u %u", &n, &p);
    int ar[n];//1st array
    for(in = 0; in < n; in++)
    {
        scanf("%u", &ar[in]);//reading the 1st array
    }
    scanf("%u", &m);
    int arr[m];//2nd array
    for(in = 0; in < m; in++)
    {
        scanf("%u", &arr[in]);//reading the 2nd array
    }
    sort(arr, m);//sorting the 2nd array
    for(in = 0; in < n; in++)
    {
        for(jn = 0; jn < m; jn++)
        {
            if(ar[in] * arr[jn] < p)
                nr++;
            else
                break;
        }
    }
    printf("%d", nr);
    return 0;
}

So i have to read ar[] and arr[] and p. This is an example:

n = 5
p = 99
ar[5] = {1, 2, 3, 4, 5}
m = 2
arr[2] = {34, 25}

The program will print 5 because 1 * 34 < 99, 1 * 25 < 99, 2 * 34 < 99, 2 * 25 < 99, 3 * 25 < 99.

This question belongs rather here: https://codereview.stackexchange.com — Jabberwocky, May 03 '17 at 09:46
@MichaelWalz do i have to delete it and ask it on codereview or can it be just moved? — Timʘtei, May 03 '17 at 10:00
@Timotei: Just sorting isn't enough, you must make use of the fact that the array is sorted. You can skip most of your inner loop by starting from where you left off before and then finding the next item in the sorted second array for which the product with the current item from the first falls below your threshold. You will traverse each array just once, but the second array will be traversed backwards. — M Oehm, May 03 '17 at 10:09
@ImranHossain I do not remember how the name of the algorithm I used but the code is in the question. — Timʘtei, May 03 '17 at 17:28

score 2 · Accepted Answer · edited May 23 '17 at 12:34

2

I assume that elements are positive.

Sort both arrays using fast sorting method (for example, library qsort()). Time complexity is O(nlogn+mlogm)
Imagine that you fill 2D table with results of multiplication. Note that every row and every column is sorted.
Find a place at the perimeter of that imaginary matrix for given number using binary search (or number itself if exists). O(log(n)+log(m))
Walk through matrix until another edge to separate bigger values from lesser values and count them. O(n+m)

Note that you should not calculate all matrix entries (to avoid quadratic complexity), just needed ones!

This is a kind of algorithm described here and here (look at the excellent picture)

edited May 23 '17 at 12:34

Community

1
1

answered May 03 '17 at 11:46

MBo

77,366
5
53
86

1

You can skip step 3 and keep the same complexity. Just start walking from top right, go to the left until the product becomes smaller, then go one down and repeat while summing up the distances to the left edge. – maraca May 03 '17 at 13:13
@maraca Yes, it was the first variant I wrote, then I just decided to show easy way to start. – MBo May 03 '17 at 13:37
@MBo I think my code is faster because it stops when a value bigger than my 'p' is found. I mean it calculates only "asnwer + 1" products. – Timʘtei May 04 '17 at 04:37
No, you are wrong. At first, you are using quadratic sorting method. Second - you algorithm checks up to M*N results, while counting problem does not require to find or output them all - just find a number. – MBo May 04 '17 at 05:25

Need a faster algorithm to count if a product is smaller than a given number

1 Answers1