Reputation: 365

maximum pairwise product fast solution

I am trying to apply a stress test on python maximum pairwise product, fast and slow algorithm. However, The fast code appears to return a wrong result in some tests. I think the problem comes from the if condition in the fast algorithm. The condition doesn't occur in some cases, though it should be applies. I wasn't able to figure out the problem. any help?

Here is the problem, I/P, O/P details:

Given a sequence of non-negative integers a0,…,an−1, find the maximum pairwise product, that is, the largest integer that can be obtained by multiplying two different elements from the sequence (or, more formally, max0≤i≠j≤n−1aiaj). Different elements here mean ai and aj with i≠j (it can be the case that ai=aj).

Input format

The first line of the input contains an integer n. The next line contains n non-negative integers a0,…,an−1 (separated by spaces).

Constraints:

2≤n≤2⋅105; 0≤a0,…,an−1≤105.

Output format:

Output a single number — the maximum pairwise product.

from random import randint
from random import randrange


def max_pairwise(n,a):
  #  n = int(input())
    res = 0
 #   a = [int(x) for x in input().split()]
    assert(len(a) == n)

    for i in range(0,n):
        for j in range(i+1,n):
            if a[i]*a[j] > res:
                res = a[i]*a[j]

    return(res)
    

def max_pairwise_fast(n,a):
 #   n = int(input())
 #   a = [int(x) for x in input().split()]

    max_index1 = -1
    max_index2 = -1

    for i in range(0,n):
        if a[i] > a[max_index1]:
            max_index1 = i
        else:
            continue

    for j in range(0,n):
        if ((a[j] != a[max_index1]) and (a[j] > a[max_index2])):
            max_index2 = j
        else:
            continue

    res = a[max_index1]* a[max_index2]
    return(res)

    
#stress_test
while(1):
    n = randint(0,9) +2
    print(n,"n")
    a = []
    for i in range (n):
        a.append(randrange(9000))
    for i in range(n):
        print(a[i],'a[i]',"/n")
    if (max_pairwise(n,a) == max_pairwise_fast(n,a)):
        print(max_pairwise(n,a), max_pairwise_fast(n,a),"true")
    else:
        print(max_pairwise(n,a), max_pairwise_fast(n,a), "false")
        break

This is an example of the result:

6 n
318 a[i] /n
7554 a[i] /n
7531 a[i] /n
7362 a[i] /n
4783 a[i] /n
4897 a[i] /n
56889174 56889174 true
5 n
6879 a[i] /n
6985 a[i] /n
8561 a[i] /n
5605 a[i] /n
3077 a[i] /n
59798585 59798585 true
9 n
8285 a[i] /n
3471 a[i] /n
2280 a[i] /n
2443 a[i] /n
5437 a[i] /n
2605 a[i] /n
1254 a[i] /n
6990 a[i] /n
2943 a[i] /n
57912150 68641225 false

Upvotes: 3

Answers (5)

Sulthonul Mubarok

Reputation: 1

With input array data: Example: [1, 2, 3]

def max(arr):
    a = 0
    b = 0
    for i in range(len(arr)):
        if a == 0 & arr[i]>a:
            a = arr[i]
        else:
            if arr[i]>a:
                b = a
                a = arr[i]
            else:
                if arr[i]>b: 
                    b = arr[i]
            
    return a*b;

Upvotes: 0

Fidele

Reputation: 19

def max_pairwise_fast(n, a):
    max_index1 = 0
    max_index2 = 0
    for i in range(n):
        if a[i] > max_index1:
            max_index2 = max_index1
            max_index1 = a[i]
        elif a[i] > max_index2:
            max_index2 = a[i]
    return max_index1 * max_index2

if __name__ == '__main__':
    input_n = int(input())
    input_numbers = [int(x) for x in input().split()]
    print(max_pairwise_fast(input_n, input_numbers))

Upvotes: -2

Divyanshu Kumar

Reputation: 11

This might not help you.
I was attempting this question at Coursera ( Assignment ) and found that we don't need to make the solution more complex. We can simply store the first two largest integers while scanning from the user and print their product. A complex solution is the main reason for the TLE error. code in c

#include<stdio.h>
int main() {
    long long n, a = 0, b = 0, i = 0, numb = 1;
    scanf("%lld", &n);
    for (i = 0; i < n; i++){
        scanf("%lld", &numb);
        if(numb >= a){
            b = a;
            a = numb;
        }
        else if(numb > b)
            b = numb;
    }
    printf("%lld", a * b);
    return 0;
}

Upvotes: 0

Reblochon Masque

Reputation: 36712

In your fast implementation, when you are finding a largest number, you must also update the second largest to the value of the previous largest, otherwise, there are cases where you end up multiplying numbers that are not the two largest.

def product_of_two_largest(seq):
    largest = float("-inf")
    second_largest = float("-inf")

    for elt in seq:
        if elt > largest:
            second_largest = largest
            largest = elt
        elif elt > second_largest:
            second_largest = elt
    return second_largest * largest

Note 1:

Your while loop must also be updated, you are calculating the values twice instead of once.

while(1):
    n = randint(0,9) +2
    print(n,"n")
    a = []
    for i in range (n):
        a.append(randrange(9000))
    for i in range(n):
        print(a[i],'a[i]',"/n")

    slow, fast = max_pairwise(n, a), two_largest_product(a)

    if (slow == fast):
        print(slow, fast, slow == fast)
    else:                                 # attention, this never happens now.
        break

Note 2:

As we are dealing with only non-negative integers, you will likely have a faster implementation if you simply sort the sequence and multiply the last two numbers (in spite of the fact that sort is O(nlogn), vs O(n) for the fast implementation above.

b = sorted(a)
print("max1 x max2 = ", b[-1] * b[-2])

Note 3:

Using a heap data structure (from collections import heap) is the theoretical best way to find the n largest items, but you'd likely need to have 100,000's of items to make it worth your while.