Stuck on a practice problem involving arrays and modifying array of array elements [closed]

Question

Closed. This question needs debugging details. It is not currently accepting answers.

Edit the question to include desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem. This will help others answer the question.

Closed 9 months ago.

Improve this question

There is a problem on Exercism I'm stuck on. I should get the multiples of a factor that are less than the limit and then add them to an array, I should do this to all factors (get their multiples array) and then combine them in a bigger array, remove the duplicates and add their sum.

I have repeated it over 3 times now and I always end up getting segmentation faults and arithmetic exceptions. The way the practice is setup, I don't get much info. Here is the header and the code:

Header:

#ifndef SUM_OF_MULTIPLES_H
#define SUM_OF_MULTIPLES_H

#include <stddef.h>

unsigned int sum(const unsigned int *factors, const size_t number_of_factors,
                 const unsigned int limit);

#endif

Actual code:

#include "sum_of_multiples.h"
#include <stdlib.h>
#include <string.h>

int get_multiples_number(unsigned int factor, unsigned int limit);
unsigned int *get_multiples_array(unsigned int factor, unsigned int limit);

unsigned int sum(const unsigned int *factors, const size_t number_of_factors, const unsigned int limit)
{
    int number_of_elements_in_all_arrays = 0;
    
    for (size_t i = 0; i < number_of_factors; i++)
    {
        number_of_elements_in_all_arrays += get_multiples_number(factors[i], limit);
    }
    unsigned int *big_array = malloc(number_of_elements_in_all_arrays * sizeof(unsigned int));

    int index = 0;
    //enter each factor and add its multiples to the big array
    for (size_t j = 0; j < number_of_factors; j++)
    {
        unsigned int *factor_multiples_array = get_multiples_array(factors[j], limit);
        int factor_multiples = get_multiples_number(factors[j], limit);

        memcpy(big_array + index, factor_multiples_array, factor_multiples * sizeof(unsigned int));
        index += factor_multiples;
        free(factor_multiples_array);
    }

    //add all big_array numbers that are not repeated;
    unsigned int sum = 0;
    unsigned int duplicated_sum = 0;

    for (int k = 0; k < index; k++)
    {
        for (int l = k + 1; l < index - 1; l++)
        {
            if (big_array[k] == big_array[l])
            {
                duplicated_sum += big_array[k];
            }
            else
            {
                sum += big_array[k];
            }
        }
    }
    return sum;
}

int get_multiples_number(unsigned int factor, unsigned int limit)
{
    int multiples = 0;
    while (factor * (multiples + 1) < limit)
    {
        multiples++;
    }
    return multiples;
}

unsigned int *get_multiples_array(unsigned int factor, unsigned int limit)
{
    int multiples = get_multiples_number(factor, limit);
    unsigned int *multiples_array = malloc(multiples * sizeof(unsigned int)); 
    
    for (int i = 0; i < multiples; i++)
    {
        multiples_array[i] = factor * (i+1);
    }
    return multiples_array;
}

One thing, you aren't making any checks of malloc() success. Another, is that unsigned int sum; seems inadequate for summing the elements of a large array, when any two elements might break it. Also this while (factor * (multiples + 1) < limit) might overflow. — Weather Vane
– Weather Vane, Commented Mar 11 at 22:48
You should try to make a minimal reproducible example that shows your problem. Then we can compile it, test it, and debug it. — pmacfarlane
– pmacfarlane, Commented Mar 12 at 0:00
Since we are missing the "driver code" that calls the "sum" function it's hard to be sure of the context, but one thing I did note when I added a simple call to the "sum" function, I noticed that memory is allocated for the "factor_multiples_array" array and then freed, but the memory that is allocated for the "big_array" is never freed when returning from the function. That would be a memory leak, and could be a large leak. If that function is called numerous times, that might be a suspect. — NoDakker
– NoDakker, Commented Mar 13 at 2:16

Alon Alush · Accepted Answer · 2025-03-13 19:03:19Z

If any element in your factors array is zero, then the loop in get_multiples_number becomes an infinite loop. For example, with a factor of 0 the condition

while (0 * (multiples + 1) < limit)

is always true (as long as limit > 0, so you never exit the loop. This will eventually lead to memory exhaustion or a segmentation fault. You can simply ignore a factor of 0 or treat it specially.

Your nested loops that try to sum the non-duplicate multiples are flawed:

In your inner loop you use for (int l = k + 1; l < index - 1; l++) . This misses checking the last element in the array and can lead to incorrect indexing.

The logic inside these loops adds the current element to either duplicated_sum or sum repeatedly, causing the same number to be added multiple times. Also, there's no mechanism to "mark" an element as already summed.

The idea of combining arrays of multiples then iterating pairwise to remove duplicates is error-prone and overcomplicates the problem. Instead, you could iterate over all numbers less than the limit and add the number to the sum if it is a multiple of any of the factors (ignoring 0). For example:

#include <stdlib.h>
#include <stdbool.h>

unsigned int sum(const unsigned int *factors, const size_t number_of_factors, const unsigned int limit) {
    unsigned int result = 0;

    bool *is_added = calloc(limit, sizeof(bool));
    if (is_added == NULL) {
        return 0;
    }

    for (size_t i = 0; i < number_of_factors; i++) {
        if (factors[i] == 0) {
            continue;
        }

        for (unsigned int multiple = factors[i]; multiple < limit; multiple += factors[i]) {
            if (!is_added[multiple]) {
                result += multiple;
                is_added[multiple] = true;
            }
        }
    }

    free(is_added); 
    return result;
}

Here, the factor 0 is ignored, each number is added only once, and the logic is simpler.

Collectives™ on Stack Overflow

Stuck on a practice problem involving arrays and modifying array of array elements [closed]

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related