Product of all but one number in a sequence

Question

I was given the following prompt in a coding interview:

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]

I solved this in two ways:

• fun multiplies all elements together in the first iteration, and then loops again and divides by the number at that position
• fun2 does not use division, and instead iteratively builds up the sum in each index

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

int fun(int* nums, int arr_size)
{
    int sum;
    int i;
    
    for(i=0, sum=1; i<arr_size; i++)
        sum*=nums[i];
    for(i=0; i<arr_size; i++)
        nums[i]=sum/nums[i];
    return 0;
}

int fun2(int* nums, int arr_size)
{
    int i,j;
    int sum=1;
    int new_arr[arr_size];
  
    for(i=0; i<arr_size; i++) {
        for(j=0; j<arr_size; j++) {
            if(i!=j)
                sum*=nums[j]; //skip member same index in the loop
        }
        new_arr[i]=sum;
        sum=1; 
    }
    memcpy(nums, new_arr, arr_size*sizeof(int));
    return 0;
}

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 i;
    fun(nums, size);
    for (i = 0; i < size; i++) 
        printf("%d ", nums[i]); 
    
    //what if you can't use division?
    printf("\n");
    int nums2[] = {1, 2, 2, 4, 6}; 
    fun2(nums2, size);
    for (i = 0; i < size; i++) 
        printf("%d ", nums2[i]);
   
    return 0;
}
```

Answer 1

Here are some things that may help you improve your code.

Use all required #includes

The code uses memcpy, so it should #include <string.h>. It might still compile on your machine, with your compiler, but it's not portable.

Think about potential errors

As one of the comments correctly notes, if one of the entries has the value of zero, this line will have a problem:

nums[i]=sum/nums[i];

Also, what happens if the passed arr_size is zero or negative? What should the function return if there is exactly one item in the array? What if the passed pointer is NULL?

Follow directions exactly

The problem says to "return a new array" but that is not really what this code is doing. This code is overwriting the input array. One of the problems with that is that it's not possible to call this with a const pointer as mentioned in the next suggestion. It also means that rather than returning a meaningless constant value in all cases, the function should probably return a pointer.

Use const where practical

As mentioned above, the code should return a new array rather than overwriting the passed one. I would suggest that the function should be something like this:

int* exclusive_product(const int* nums, size_t nums_size)

Note that first, we use const and second, we use size_t rather than int for the second argument to more clearly indicate the type of variable we are expecting.

Use better variable names

I would say that nums, size and i are good variable names, but that fun and fun2 and definitely sum are not. The problem is that fun doesn't tell the reader anything about what the code is supposed to do and sum is actually misleading (it's a product, not a sum).

Think about an efficient way to solve this

The \$O(n^2)\$ code you have in fun2 is not a terrible way to solve the problem and has the advantage of being obviously correct. When I interview people, I typically like such answers because it's much easier to make slow correct code fast than it is to make fast incorrect code correct. However, in a good interview, I like to ask the candidate to make comments on his or her own code, including any limitations, assumptions or potential improvements that might be made. In this case, it helps if we think mathematically about the final values in the resulting array \$B\$ from input array \$A\$. For example, we know that every value \$B_j\$ can be expressed as the product $$\displaystyle B_j = \prod_{i=0}^{j-1} A_i \prod_{i=j+1}^{n-1} A_i$$ if \$n\$ is the length of the array. This suggests a more efficient approach I'll leave for you to figure out.

Answer 2

As mentioned by a commenter on the question, neither version satisfies the requirement to return a new array. I'll leave that for you to fix yourself (demonstrating your understanding of memory allocation to your interviewer).

The division version requires some modification to work when one or more inputs are zero. I suggest keeping track of the position of any zero that is found on the first pass - if a second zero is found, all the results will be zero, and if a single zero is found, then all the results except at that position will be zero.

That looks a bit like this:

void fun(int *nums, int arr_size)
{
    int product = 1;
    int zero_pos = -1;

    for (int i = 0;  i < arr_size;  i++) {
        if (nums[i]) {
            product *= nums[i];
        } else if (zero_pos < 0) {
            zero_pos = i;
        } else {
            product = 0;
            break;
        }
    }

    if (zero_pos < 0) {
        for(int i = 0;  i < arr_size;  i++) {
            nums[i] = product / nums[i];
        }
    } else {
        for (int i = 0;  i < arr_size;  i++) {
            nums[i] = (i == zero_pos) ? product : 0;
        }
    }
}

I haven't made any attempt to deal with the risk of signed integer overflow in this code; that's as much a risk as it is in your original.

There are some problems in fun2(): failure to include <string.h> for the use of memcpy() is the most serious there.

We should use an unsigned type (probably size_t) for the size parameter. That also means that we don't have mixed-signedness arithmetic where we multiply by sizeof. Although having said that, we don't need to multiply - we can simply use sizeof new_arr (the whole array) and the compiler will manage that for us.

We can also reduce the scope of several of the variables:

#include <string.h>
void fun2(int *nums, int arr_size)
{
    int new_arr[arr_size];

    for (int i = 0;  i < arr_size;  i++) {
        int product = 1;
        for (int j = 0;  j < arr_size;  j++) {
            if (i != j) {
                product *= nums[j];
            }
        }
        new_arr[i]=product;
    }
    memcpy(nums, new_arr, sizeof new_arr);
}

Answer 3

Overflow

Certainly the product of many int can overflow ---> leading to udenfined bahavior (UB).

If an additional specification included "the product does not overflow", we still have a problem with fun(). That approach may overflow the intermediate product sum.

A work around is to use long long or intmax_t for sum.

Code could use a compile time check

#if LLONG_MAX/INT_MAX < INT_MAX
  #error "int lacks a 2x wide type."
#endif

Zero

A simple improvement would handle num[i] == 0 and certainly not divide by zero. If that occurs more than once, the resultant array is all zeros. With only 1 num[i] == 0, all other elements are zero, and the one i ellement is the product of the rest.

C2x

C2X promotes the idiom of coding with the array size first.

// int fun(int* nums, int arr_size)
int fun(int arr_size, int* nums)

int vs. size_t

Array sizes may exceed INT_MAX. Consider size_t for the size. Keep in mind that size_t is an unsigned type.

int* nums or int *nums

C standard uses style int *nums. Follow your group's style standard.

Return value

Perhaps use the return value for something useful. Perhaps: detect overflow.

Keep for() clean

Avoid over-packing for(). As with such coding style issue, follow group's standards.

// for(i=0, sum=1; i<arr_size; i++)
sum = 1;
for(i=0; i<arr_size; i++)
// of better, declare when needed
int sum = 1;
for(int i=0; i<arr_size; i++)

Example

Unchecked code - will review later

// Return NULL out-of-memory or overflow.
int fun(size_t arr_size, const int *nums) {
  int *parray = calloc(arr_size, sizeof *parray);
  if (parray == NULL) {
    return parray;
  }

  int *zero = NULL;
  intmax_t product = 1;
  bool overflow = false;
  
  for (size_t i = 0; i < arr_size; i++) {
    if (nums[i]) {
      overflow |= mult_check(nums[i], &product);
    } else {
      if (zero) {
        return parray; // We are done, 2 zeros found
      }
      zero = &nums[i];
    }
  }

  for (size_t i = 0; i < arr_size; i++) {
    int divisor = nums[i] ? nums[i] : 1; 
    intmax_t q = product/divisor;
    if (q < INT_MIN || q > INT_MAX) {
      overflow = true;
      break;
    } 
  }

  if (overflow) {
    free(parray);
    return NULL;
  }

  return parray;
}

Answer 4

Thank you all for your helpful responses. I am posting a better solution here with taking into consideration the suggestions of [Edward], [CiaPan], [chux], [superb rain] and others suggestions.

#include <stdio.h>
#include <stdlib.h>
#include <string.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;
}

It would be helpful if you give further improvements too.