Small Steps III — Thinking with Programs

Challenges (Optional)

Challenges (Optional)

Explore one topic in small steps. Try the examples one at a time and take a break whenever you need. Choose how many extra exercises you want to try.

Finding the second-largest value

What you will learn

Before solving a new problem, define what counts as the answer and what assumptions hold about the input. Here we remember two candidates.

Try it

Example · example1.cpp
void small_main()
{
    Array<int> numbers = {8, 3, 12, 5, 10};

    int largest = numbers[0];
    int second = numbers[1];

    if (second > largest)
    {
        int temp = largest;
        largest = second;
        second = temp;
    }

    for (int i = 2; i < numbers.length(); i = i + 1)
    {
        if (numbers[i] > largest)
        {
            second = largest;
            largest = numbers[i];
        }
        else if (numbers[i] > second)
        {
            second = numbers[i];
        }
    }

    print("Second largest: ", second);
}

The example assumes at least two elements and includes duplicates in the ranking. For {9, 9, 3}, the answer is 9. It does not mean the second distinct value.

When a new maximum appears, move the previous maximum into second. For 8, 3, 12, 5, 10, the answer is 10.

Counting occurrences of the largest value

What you will learn

Combining two procedures you already know can solve a new problem.

Try it

Example · challenge_2_example2.cpp
void small_main()
{
    Array<int> numbers = {4, 9, 2, 9, 7};

    int largest = numbers[0];
    int count_largest = 0;

    for (int i = 0; i < numbers.length(); i = i + 1)
        if (numbers[i] > largest)
            largest = numbers[i];

    for (int i = 0; i < numbers.length(); i = i + 1)
        if (numbers[i] == largest)
            count_largest = count_largest + 1;

    print("Largest: ", largest);
    print("How many: ", count_largest);
}

First find the maximum, then use a second loop to count elements equal to it. The output is Largest: 9 and How many: 2.

Make each step's responsibility clear before trying to combine the two loops. The array must contain at least one element.

Exercise

Assume there are at least two distinct values and find the second-smallest value.

Exercise starter · exercise1_starter.cpp
void small_main()
{
    Array<int> numbers = {8, 3, 12, 5, 10};

    // find the second smallest value.
}

Hint

Remember smallest and second. When a value is smaller than smallest, update both values together.

show solution
void small_main()
{
    Array<int> numbers = {8, 3, 12, 5, 10};

    int smallest = numbers[0];
    int second = numbers[1];

    if (second < smallest)
    {
        int temp = smallest;
        smallest = second;
        second = temp;
    }

    for (int i = 2; i < numbers.length(); i = i + 1)
    {
        if (numbers[i] < smallest)
        {
            second = smallest;
            smallest = numbers[i];
        }
        else if (numbers[i] < second)
        {
            second = numbers[i];
        }
    }

    print(second);
}
Try More (Optional)

Exercise

First find the Array's largest value, then count how often it occurs in a second loop.

Exercise starter · challenge_2_exercise2_starter.cpp
void small_main()
{
    Array<int> numbers = {5, 9, 2, 9, 9, 4};

    // find largest, then count it.
}

Hint

The first loop finds largest; the second counts occurrences of numbers[i] == largest.

show solution
void small_main()
{
    Array<int> numbers = {5, 9, 2, 9, 9, 4};
    int largest = numbers[0];

    for (int i = 1; i < numbers.length(); i = i + 1)
        if (numbers[i] > largest)
            largest = numbers[i];

    int count = 0;

    for (int i = 0; i < numbers.length(); i = i + 1)
        if (numbers[i] == largest)
            count = count + 1;

    print("Largest: ", largest);
    print("Count: ", count);
}
← Previous lessonNext lesson →