Product of all but one number in a sequence - Follow Up

Question

This question is a follow up question to the Product of all but one number in a sequence.

I am posting a new code here with taking into consideration the suggestions of [Edward], [CiaPan], [chux], [superb rain] and others. Please advise how the code efficiency can be improved.

#include <stdio.h>
#include <stdlib.h>    

//without division, with O(n) time, but extra space complexity as suggested
//return new array on the heap 
int *find_product_arr(const int *nums, int arr_size)
{
    int *new_arr = (int *)malloc(sizeof(int)*arr_size);

    int mult_prefix=1; //product of prefix elements
    int mult_suffix=1; //product of suffix elements
    
    //left most element special handling
    new_arr[0]=1;
    
    //swipe up 
    for(int i=1; i<arr_size; i++) {
        mult_prefix *= nums[i-1];
        new_arr[i] = mult_prefix;
    }
    
    //swipe down
    for(int j=arr_size-2; j>=0; j--) {
        mult_suffix *= nums[j+1];
        new_arr[j] *= mult_suffix;
    }
        
    return new_arr;
}


int main(void)
{
    /*Given an array of integers, return a new array such that each element at index i of the 
    new array is the product of all the numbers in the original array except the one at i.
    For example, if our input was [1, 2, 3, 4, 5], the expected output would be 
    [120, 60, 40, 30, 24] */
    int nums[] = {1, 2, 2, 4, 6};    
    int size = sizeof(nums)/sizeof(nums[0]);
    
    int *products = find_product_arr(nums, size); //get a new array
    
    for (int i = 0; i < size; i++) 
        printf("%d ", *(products+i) ); 
    
    free(products); //release heap memory
   
    return 0;
}

Answer 1

You could eliminate the special case here:

//left most element special handling
new_arr[0]=1;

//swipe up 
for(int i=1; i<arr_size; i++) {
    mult_prefix *= nums[i-1];
    new_arr[i] = mult_prefix;
}

by assigning before multiplying, and bringing index 0 into the loop:

//swipe up 
for(int i=0; i<arr_size; i++) {
    new_arr[i] = mult_prefix;
    mult_prefix *= nums[i];
}

A similar transformation also applies to the downward sweep (so that each iteration only accesses nums[i], making it easier to reason about).

There is a cost associated with the simplification: an extra multiply, and risk of overflow (technically Undefined behaviour, even though we don't use the final value).

Answer 2

The algorithm is optimal, and any perceived inefficiency in expression should not faze the compiler at least. So, it will all be about optimizing for readability and maintenance.

Naming

There are three factors for choosing names:

• Being consistent (with the rest of the code, and the field's jargon),
• being concise (all else being equal, less is more), and
• being descriptive.

Infrequent use and big scope call for more descriptive identifiers, even if conciseness suffers. Properly choosing what to describe and being precise about it is crucial.

1. find_product_arr() is a miss-nomer. There is no finding about it, but calculation, or derivation. And if product is pluralized, the awkward abbreviation for array can also be dropped, as it is implied. Thus, better name it like derive_products().

2. arr_size is also a bad one. Where is arr? new_arr might be an implementation-detail, not that the user should look or care, as it is not part of the public interface. A simple count would be best, count_nums would also serve.

3. new_arr also doesn't describe anything relevant. I would call it result, res, or just r. I prefer the shortest as it is a very common identifier in my code.

4. mult_prefix and mult_suffix suffer from a far over-broad scope. The compiler might not care, but we do. Tightening the scope to just the relevant for-loop lets us rename both to mult.

5. Be precise: Do you have a size (what is the unit of measurement? Bytes is common), or a count.

Allocating memory

int *new_arr = (int *)malloc(sizeof(int)*arr_size);

6. The above line uses sizeof(TYPE), which is error-prone as it repeats information manually derived from the left hand side. Use sizeof *pointer and let the compiler figure it out.

7. "Do I cast the result of malloc? "
   No, not in C, as it is superfluous and error-prone.

8. Always check the result of malloc(). It can fail.

Fixed code:

int* r = malloc(count * sizeof *r);
if (!r && count)
    return 0; // or die("alloc() failed in ABC.\n"); which should call vfprintf and abort

Use indexing when you mean it

printf("%d ", *(products+i) );

9. I really wonder why you didn't use normal indexing products[i] instead of *(products+i) in main() like everywhere else.

The rest

10. In a definition, marking the absence of parameters with void is not needed. Make of it what you will.

11. return 0; is implicit for main() since C99. Not sure you should care.

Answer 3

This "new" vs. "original" array seems a bit unclear to me. This is C, so you have to define very carefully. The strdup() states at the very top:

Memory for the new string is obtained with malloc(3), and can be freed with free(3).

Maybe it is the "find_" in find_product_arr() that is misleading.

And then - after correctly returning that new array(-pointer) - why:

*(products+i) and not

products[i] ?

This is like telling your new boss: OK, I made that function allocate like strdup(), but for me it still is just a pointer, whose memory I have to manage.

I minimalized nums[] and wrapped 12 loops around the function call (I gave it a new name). To "close' the loop I had to use memcpy(). If the free() is after the looping, then products gets a new address in every iteration.

int nums[] = {1,2,1};
int size = sizeof(nums) / sizeof(nums[0]);

int *products;
int loops=12;
while (loops--) {

    products = dup_product_arr(nums, size);

    for (int i = 0; i < size; i++)
        printf("%d ", products[i]);
    printf("\n");

    memcpy(nums, products, sizeof(nums));
    free(products);
}

The output:

2 1 2 
2 4 2 
8 4 8 
32 64 32 
2048 1024 2048 
2097152 4194304 2097152 
0 0 0 
0 0 0 
0 0 0 
0 0 0 
0 0 0 
0 0 0 

So this overflow problem exists...but then again that multiply-all-rule is a bit exotic. Is it meant to run on floating point numbers? Close to 1.0?

---

The combined swipe-up and swipe-down algorithm is very nice. But otherwise, because of unclear specification or over-interpretation, I don't like the result that much.

In an interview situation I hope there was the possibility to clear this "new array" question, and then I would prefer like:

  int nums[] = {1, 2, 2, 4, 6};    
  int size = sizeof(nums)/sizeof(nums[0]);
  int prods[size];
  swipe_product_into(nums, size, prods);

i.e. the function receives two arrays and the size. Both arrays are "allocated" automatically in main, without malloc/free.

Answer 4

The code is much improved from the previous version. Well done! Here are a few more things that may help you further improve your code.

Don't cast result of malloc

The malloc call returns a void * and one of the special aspects of C is that such a type does not need to be cast to be converted into another pointer type. So for example, this line:

int *new_arr = (int *)malloc(sizeof(int)*arr_size);

could be shortened to this:

int *new_arr = malloc(arr_size * sizeof *new_arr);

Note also that we don't need to repeat int here. This makes it easier to keep it correct if, for example, we wanted to change to long *.

Check the return value of malloc

If the program runs out of memory, a call to malloc can fail. The indication for this is that the call will return a NULL pointer. You should check for this and avoid dereferencing a NULL pointer (which typically causes a program crash).

Eliminate special handling

Instead of this:

//left most element special handling
new_arr[0]=1;

//swipe up 
for(size_t i=1; i<arr_size; i++) {
    mult_prefix *= nums[i-1];
    new_arr[i] = mult_prefix;
}

//swipe down
for(long j=arr_size-2; j>=0; j--) {
    mult_suffix *= nums[j+1];
    new_arr[j] *= mult_suffix;
}

Here's how I'd write it:

static const int multiplicative_identity = 1;
// calculate product of preceding numbers for each i
for (size_t i = arr_size; i; --i) {
    *result++ = prod;
    prod *= *nums++;
}
prod = multiplicative_identity;
// calculate product of succeeding numbers for each i, 
// starting from the end, and multiply by current index
for (size_t i = arr_size; i; --i) {
    *(--result) *= prod;
    prod *= *(--nums);
}
return result;

There are a couple of things worth noting here. First, is that there is no need for a special case when written this way. Second, the use of pointers simplifies the code and makes it more regular. Third, many processors have a special instruction for looping down and/or checking for zero which tends to make counting down ever so slightly faster than counting up. Fourth, there is no reason not to use the passed value nums as a pointer since the pointer is a local copy (even though the contents are not). In this particular case, since we increment the pointer to the end, moving the other direction is trivially simple since the pointers are already where we need them for both result and nums.

Consider a generic version

What if we wanted to create a similar function, but one that does the sum instead of the product? It's not at all needed for this project, but worth thinking about because of both the mathematics and the code. You will see that I called the constant multiplicative_identity. Simply put, an identity element of an operation over a set is the value that, when combined by the operation with any other element of the set yields the same value. So for example, \$n * 1 = n\$ for all real values of \$n\$ and \$n + 0 = n\$ for all real values of \$n\$. This suggests a generic routine:

int* exclusive_op(const int* nums, size_t arr_size, int (*op)(int, int), int identity)
{
    int* result = malloc(arr_size * sizeof(int));
    if (result == NULL || arr_size == 0) {
        return NULL;
    }
    int prod = identity;
    // calculate op of preceding numbers for each i
    for (size_t i = arr_size; i; --i) {
        *result++ = prod;
        prod = op(prod, *nums++);
    }
    prod = identity;
    // calculate op of succeeding numbers for each i, 
    // starting from the end, and multiply by current index
    for (size_t i = arr_size; i; --i) {
        --result;
        *result = op(*result, prod);
        prod = op(prod, *(--nums));
    }
    return result;
}

Now we can define functions with which to use this generic version:

int add(int a, int b) { 
    return a+b;
}

int mult(int a, int b) { 
    return a*b;
}

int multmod3(int a, int b) { 
    return (a*b)%3;
}

int summod3(int a, int b) { 
    return (a+b)%3;
}

struct {
    int (*op)(int, int); 
    int identity;
} ops[] = {
    { mult, 1 },
    { add, 0 },
    { multmod3, 1 },
    { summod3, 0 },
};

Using that array of structs, we could produce the same effect as your find_product_arr by using this wrapper function:

int *generic(const int *nums, size_t arr_size) {
    return exclusive_op(nums, arr_size, ops[0].op, ops[0].identity);
}

As you can see with the last two functions, this works with any operation that is both associative and that has an identity value.

Create some test code

How do you know if your results are correct? One way to do that is to write some test code. As I commented on your earlier code, it wasn't very efficient but was obviously correct. That is a nice foundation on which to create test code to make sure that your new version still produces correct results. Here's one way to do that. First, we need a way to compare the returned result against a known correct version:

bool compare(size_t size, const int* result, const int* expected)
{
    for (size_t i = 0; i < size; ++i) {
       if (result[i] != expected[i]) {
           return false;
       }
    }
    return true;
}

Now we can get fancy with colors and a test array:

#define RED    "\033[31m"
#define GREEN  "\033[32m"
#define WHITE  "\033[39m"

int main(void)
{
    struct {
        size_t array_size;
        int in[5];
        int expected[5];
    } test[] = {
        { 5, { 1, 2, 3, 4, 5 }, { 120, 60, 40, 30, 24 } },
        { 4, { 1, 2, 3, 4, 5 }, { 24, 12, 8, 6, 0 } },
        { 3, { 1, 2, 3, 4, 5 }, { 6, 3, 2, 0, 0 } },
        { 2, { 1, 2, 3, 4, 5 }, { 2, 1, 0, 0, 0 } },
        { 1, { 1, 2, 3, 4, 5 }, { 1, 0, 0, 0, 0 } },
        { 1, { 0, 2, 3, 4, 5 }, { 1, 0, 0, 0, 0 } },
        { 5, { 1, 2, 2, 4, 5 }, { 80, 40, 40, 20, 16 } },
        { 5, { 9, 2, 2, 4, 5 }, { 80, 360, 360, 180, 144 } },
        { 5, { 0, 2, 0, 4, 5 }, { 0, 0, 0, 0, 0 } },
        { 5, { 7, 2, 0, 4, 5 }, { 0, 0, 280, 0, 0 } },
        { 5, { -1, -1, -1, -1, -1 }, { 1, 1, 1, 1, 1 } },
        { 4, { -1, -1, -1, -1, -1 }, { -1, -1, -1, -1, -1 } },
        { 2, { INT_MAX, INT_MIN, 0, 0, 0 }, { INT_MIN, INT_MAX, 0, 0, 0 } },
    };
    const size_t test_count = sizeof(test)/sizeof(test[0]);

    const char* function_names[] = { "original", "find_product_arr", "generic" };
    int *(*functions[])(const int*, size_t) = { original, find_product_arr, generic };
    const size_t function_count = sizeof(functions)/sizeof(functions[0]);

    for (size_t i = 0; i < test_count; ++i) {
        for (size_t j = 0; j < function_count; ++j) {
            int *result = functions[j](test[i].in, test[i].array_size);
            bool ok = compare(test[i].array_size, result, test[i].expected);
            printf("%s: %20.20s  { %lu, {",
                (ok ? GREEN " OK" WHITE: RED "BAD" WHITE),
                function_names[j],
                test[i].array_size
            );
            dump(test[i].in, test[i].array_size);
            printf("}, {");
            dump(test[i].expected, test[i].array_size);
            printf("} }");
            if (ok) {
                printf("\n");
            } else {
                printf(", got " RED "{" );
                dump(result, test[i].array_size);
                printf("}" WHITE "\n");
            }
            free(result);
        }
    }
}

Is it overkill? Probably, but if I saw such code associated with a function like yours, I'd be much more likely to both use it as is with confidence and also to modify it or write a new version with the expectation of being able to test it quickly and accurately.