Question:

Implement a void function F that takes pointers to two arrays of integers (A and B) and a size N as parameters. It then populates B where B[i] is the product of all A[j] where j != i.

For example: if A = {2, 1, 5, 9}, then B would be {45, 90, 18, 10}

Answer:

This problem seems easy at first glance so a careless developer might write something like this:

void F(int* A, int* B, int N) {
    int m = 1;
    for (int i = 0; i < N; ++i) {
        m *= A[i];
    }
    
    for (int i = 0; i < N; ++i) {
        B[i] = m / A[i];
    }
}

This will work for the given example, but when you add a 0 into input array A, the program will crash because of division by zero. The correct answer should take that edge case into account and look like this:

void F(int* A, int* B, int N) {
    int m = 1;
    int numZero = 0;
    int zeroIndex = -1;
    
    
    for (int i = 0; i < N; ++i) {
        B[i] = 0;
        if (A[i] == 0) {
            ++numZero;
            zeroIndex = i;
        } else {
            m *= A[i];
        }
    }
    
    if (numZero == 0) {
        for (int i = 0; i < N; ++i) {
            B[i] = m / A[i];
        }
        return;
    }
    
    if (numZero >= 2) {
        return;
    }
    
    B[zeroIndex] = m;
}

The presented solution above has a Big O complexity of O(n). While there are simpler solutions available (ones that would ignore the need to take 0 into account), that simplicity has a price of complexity, generally running significantly slower.


Keywords:

© 2017 QuizBucket.org