The Interview Question Today#15(10-3-19)

Question:
Given an array a, we have to find maximum product possible with the subset of elements present in the array.

Examples:

Input : a[] = { -1, -1, -2, 4, 3 }
Output : 24( Maximum product will be ( -2 * -1 * 4 * 3 ) = 24)

Approach:

1. If there are even number of negative numbers and no zeros, the result is simply a product of all
2. If there are an odd number of negative numbers and no zeros, the result is the product of all except the largest valued negative number.
3. If there are zeros, the result is the product of all except these zeros with one exceptional case. The exceptional case is when there is one negative number and all other elements are 0. In this case, the result is 0.

C program 

#include <stdio.h>

int maxProductSubset(int a[], int n)

{

    if (n == 1)

        return a[0];

    // Find count of negative numbers, count of zeros, maximum valued negative number

    // and product of non-zero numbers

    int max_neg =-999;

    int count_neg = 0, count_zero = 0;

    int prod = 1,i;

    for ( i = 0; i < n; i++) {

        // If number is 0, we don't multiply it with product.

        if (a[i] == 0) {

            count_zero++;

            continue;

        }

        // Count negatives and keep track of maximum valued negative.

        if (a[i] < 0) {

            count_neg++;

            max_neg = max(max_neg, a[i]);

        }

        prod = prod * a[i];

    }

    if (count_zero == n)

        return 0;

    if (count_neg & 1) {

        // Exceptional case: There is only negative and all other are zeros

        if (count_neg == 1 &&

            count_zero > 0 &&

            count_zero + count_neg == n)

            return 0;

        // Otherwise result is product of all non-zeros divided by maximum valued negative.

        prod = prod / max_neg;

    }

    return prod;

}

int max(int a,int b){

if(a>b)

{

    return a;

}

return b;

}

int main()

{

    int arr[100];

    int n,i;

       printf("Enter the Number of Elements present: ");

    scanf("%d",&n);

    printf("\nEnter the values of Elements");

    for(i=0;i<n;i++)

    {

        printf("\nElements %d:",i+1);

        scanf("%d",&arr[i]);

    }

    printf("Maximum Product= %d",maxProductSubset(arr, n));

    return 0;

}

Output:

Enter the Number of Elements present: 5

Enter the values of Elements

Elements 1:1

Elements 2:2

Elements 3:0

Elements 4:-1

Elements 5:-2

Maximum Product= 4