c++ - 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 << '
';

    return 0;
}

question from:https://stackoverflow.com/questions/65887747/the-minimum-number-of-applications-of-the-process

Answer 1

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).