The minimum number of applications of the process?

Question

The apples from Dorel's orchard had an excellent year. He wants to harvest all the fruits but feeling overwhelmed, he resorts to a strategy like this: he chooses as large a sequence of trees as possible from which he harvests the same amount of apples. The procedure is applied until all the apples are harvested.

Calculate the minimum number of applications of the process so that all apples are harvested.

Input data:

The number of trees

How many apples are in each tree

Output data:

Minimum number of applications of the collection procedure

Example:

Input data

4

3 2 4 2

Output data

3

Test 3: Test #3 Incorrect program output --- Input --- 60 17 27 20 44 22 18 30 32 26 36 39 16 42 37 25 28 31 35 34 29 41 24 21 19 38 45 15 40 33 43 45 54 59 51 49 46 53 50 47 48 58 56 55 52 57 59 58 57 60 56 60 59 57 58 56 59 57 60 58 56 --- Program output --- 22

--- Expected output (numbers)--- 57

and other 3 tests failed....

I know that it s a problem


using namespace std;

int minim(int* v, int n)
{
    int i, min;
    for (i = 0; i < n; i++)
        if (v[i] != 0)
            min = v[i];

    for (;i < n; i++)
        if (min > v[i] && v[i] != 0)
            min = v[i];
    return min;
}

bool toateZero(int* v, int n)
{
    for (int i = 0; i < n; i++)
        if (v[i] != 0)
            return false;
    return true;
}

void scadeMin(int* v, int n)
{
    int min = minim(v, n);
    for (int i = 0; i < n; i++)
        if(v[i] >= min)
            v[i] -= min;
}

int main()
{
    int n;

    cin >> n;

    int* v = new int[n];

    for (int i = 0; i < n; i++)
        cin >> v[i];

    int count = 0;
    while (!toateZero(v, n))
    {
        scadeMin(v, n);
        count++;
    }
    cout << count << '\n';

    return 0;
}

This reads like it's from some contest/challenge/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. Other than that, there's nothing here that actually improves one's knowledge of C++. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Jan 25 '21 at 15:43
in `minim`, for the second loop, `i` is not initialized. Are you sure that is what you want to do? — Zois Tasoulas, Jan 25 '21 at 15:43
@Sam Varshavchik It s from an exam, but I m not asking for the full problem, I'm asking to know what s wrong. — Criss Barbu, Jan 25 '21 at 15:47
@CrissBarbu Are you sure this is the expected output for the input you shared? Also, you are not freeing in `main` the memory you allocate for the array. — Zois Tasoulas, Jan 25 '21 at 16:10
Wait, from an exam? Are you allowed to ask others for help on your exam? Or are you required to solve the problem yourself, with no outside help? What kind of exam allows someone to ask someone else to help them with? Did you get permission from your instructor to post this to Stackoverflow? — Sam Varshavchik, Jan 25 '21 at 17:29

score -1 · Accepted Answer · answered Jan 25 '21 at 15:46

I do not understand the logic of your code. There might be more issues, but this cannot be correct:

int i, min;
for (i = 0; i < n; i++)
    if (v[i] != 0)
        min = v[i];

for (;i < n; i++)
    if (min > v[i] && v[i] != 0)
        min = v[i];

The first loop stops when i<n is false, but if i<n is false then the second loop is never entered. minim always returns the last element of v that is not 0 (result of the first loop, while the second loop does literally nothing). Getting the smallest non-zero element (or 0 when there is none) can be done like this:

int minim(int* v, int n)
{
    int min = 0;
    int i = 0;
    // get the first non-zero element
    while ( i < n && v[i] == 0) i+=1;
    // check the rest
    for ( ; i < n; ++i) {
        if (v[i] != 0 && v[i] < min ) min = v[i];
    }
    return min;
}

I advise you to use std::vector instead of a manually managed dynamic array. Also looing into the standard algorithms library is worthwhile (eg std::min_element would be a start).

The minimum number of applications of the process?

1 Answers1