Module assignment: a sensor log report

Why this assignment

This assignment brings the whole module together in one program. You will count, add, find a longest run, count pairs, reverse a number and read input until the data ends. Each part of the report uses a loop pattern from the lessons, so you will practise the choice of loop as well as the loop itself. Interviewers often give a problem like this as a take-home task, so the habits it builds matter beyond this course: clear state, careful edge cases and a stated cost.

You will not be graded on speed. You will be graded on correct output for the inputs the spec describes, and on whether your code handles the edge cases that the spec names. Read the whole assignment before you write any code. Then work through the steps in order.

The story

A small factory has a sensor on a machine. The sensor records one reading every few seconds, and each reading is a whole number that can be negative. At the end of a shift, the engineer pastes the readings into a program and asks for a short report. The report answers five questions. How many readings are there? What is their total? What is the longest stretch of identical readings, which may mean the sensor was stuck? How many pairs of readings add up to a target value that the engineer chose? And what is the reversed digit form of the total, which the engineer uses as a quick check code?

Your job is to write the program that prints this report.

The input

The program reads from standard input, which is the Input box when you run in the browser. The input has three parts, in this order.

• Line 1: one integer n, where 1 <= n <= 200. This is the number of readings.
• Line 2: n integers separated by spaces. Each reading is between -100000 and 100000 inclusive.
• Line 3: one integer target, where its absolute value is at most 200000.

The input may have extra spaces or line breaks between numbers. Reading with cin >> handles that for you, so you do not need to parse the lines yourself.

The output

The program prints exactly five lines, in this order, with one space between each word and each number. Do not print any other text. Do not print a blank line at the end, except for the newline that endl adds to the last line.

count N
sum S
longest-run L V
pairs P
reversed-sum R

Here is what each line means:

• count N is the number of readings, which is the value of n.
• sum S is the total of all the readings. The total may be negative, and it may be too big for an int, so use long long.
• longest-run L V is the length L of the longest stretch of equal readings that sit next to each other, and the value V of that stretch. If two stretches tie for the longest length, report the one that comes first in the list.
• pairs P is the number of pairs of positions (i, j) with i < j whose two readings add up to target. Two equal readings at different positions count as two different pairs.
• reversed-sum R takes the total S, ignores its sign, reverses its digits, and then puts the sign back. A total of 1200 becomes 21, and a total of -4 stays -4. A total of 0 gives 0.

Worked examples

Read these three examples carefully. Your program must print exactly the lines shown.

Example 1. The input is:

6
3 3 1 1 1 2
5

The output is:

count 6
sum 11
longest-run 3 1
pairs 2
reversed-sum 11

The total is 3 + 3 + 1 + 1 + 1 + 2, which is 11. The longest run is the three 1s in a row, so the length is 3 and the value is 1. The pairs that add up to 5 are the two 3s with the 2, so there are 2 pairs. The reversal of 11 is 11.

Example 2. This example has negative readings and a target that matches only one pair. The input is:

4
-7 -7 0 10
10

The output is:

count 4
sum -4
longest-run 2 -7
pairs 1
reversed-sum -4

The total is -7 - 7 + 0 + 10, which is -4. The longest run is the two -7s, so the length is 2 and the value is -7. The only pair that adds up to 10 is 0 and 10, so the count is 1. The reversal of the absolute value 4 is 4, and the sign is put back to give -4.

Example 3. This one has a longer run and a total that reverses to a different number. The input is:

8
120 340 340 340 9 -51 0 120
120

The output is:

count 8
sum 1218
longest-run 3 340
pairs 2
reversed-sum 8121

The total is 1218. The run of three 340s is the longest, and no other run is as long. The pairs that add up to 120 are the 120 at position 0 with the 0 at position 6, and the 0 at position 6 with the 120 at position 7. The reversal of 1218 is 8121.

The requirements checklist

Use this list while you work. Tick each item only when you have tested it. Copy the list into a comment at the top of your program if that helps you keep track.

• The program reads n, then n readings, then target, all with cin.
• The first line printed is count N, where N is the value read for n.
• The sum is stored in a long long and printed as a signed number.
• The longest run is found with a loop that walks the list once, and the first longest run wins ties.
• The pair count uses nested loops with the inner loop starting at the outer position plus one, so each pair is counted once.
• The reversed sum keeps the sign, and it prints 0 for a total of 0.
• The reversal loop runs at least once, so a total of 0 is handled.
• Your program compiles with g++ -std=c++17 -Wall and prints no warnings.
• You tested the three examples, and their output matched exactly.
• You tested the edge cases listed in the next section.

Edge cases you must test

A solution that passes the examples can still fail on other inputs. Test each of these cases with your own inputs. Work out the expected output on paper before you run the program, so you know what to compare against.

• n equal to 1. The longest run is that single reading, and the pair count is 0.
• All readings equal, such as 4 readings of 5. The longest run covers the whole list.
• A total of exactly 0. The reversed sum must print 0, not an empty line or a crash.
• A negative total with trailing zeros after reversal, such as a total of -1200. The reversed sum is -21.
• A target that no pair reaches. The pair count is 0.
• A target that many pairs reach. Two equal readings must each count, so a list of four readings of 2 with target 4 gives 6 pairs.
• Readings at the largest allowed value. The sum of 200 readings of 100000 is 20000000, which an int can hold, but use long long anyway, because the rule is that the sum must never overflow.

Scoring rubric

Your grade depends on how many of the five lines are correct, and on how well the code handles the edge cases. The three bands below describe what each level looks like.

60 percent: the core works. The program reads the input and prints the count and the sum correctly for every input. It prints the reversed sum correctly for positive totals. The longest-run and pair lines may be wrong for some inputs, but the program still prints all five lines in order and compiles without errors. A solution at this level usually misses the tie rule for the longest run, or double counts pairs.

80 percent: the report is right for normal inputs. All five lines are correct for the three examples and for most ordinary inputs. The pair count is correct, with each pair counted once. The reversed sum is correct for positive totals. Negative totals may print the wrong sign or a reversal with the sign applied twice. A solution at this level usually fails one or two of the edge cases listed above.

100 percent: correct for every legal input. All five lines are correct for every input the spec allows, including the edge cases. The reversal keeps the sign and handles 0. The longest run follows the tie rule. The code uses the loops that fit each part, with clear variable names and comments that explain the state, and it compiles with -Wall and no warnings. A 100 percent solution is one you could explain line by line in an interview.

Step-by-step plan

Build the program in four steps, and test each step before you move on. The next four sections each contain a small complete program that does one step, and you can run it in the lesson. Your final program combines them.

Step 1: read the input, print the count and the sum

Start with the reading. Read n with cin, then read n values into a vector<long long>, then read the target. Print the count. Then add the values with a for loop, starting the sum at 0. Test with Example 1 and check that the first two lines are right.

Run this program with the input from Example 1 (type 6, then 3 3 1 1 1 2, then 5, each on its own line in the Input box):

The output is:

count 6
sum 11

Notice that the target is read even though this step does not use it yet. If you forget to read it, the later steps will break, because the input is read in order. Always read every value the spec lists, even when the current step does not need it.

Step 2: the longest run

The longest run needs a loop that moves from one run to the next. Use an outer while loop that moves from one run to the next, and an inner while loop that moves forward while the value stays the same. Each time a run ends, compare its length with the best so far. Use a strict > comparison, so that the first run wins a tie.

Run this program with Example 1 as input. Use the same three-line input as in step 1:

The output for Example 1 is:

longest-run 3 1

Trace the outer loop. It starts at position 0, where the run is the two 3s, so j moves to 2 and the run length is 2. That is the best so far. The next run starts at position 2, which holds 1, and its run is three 1s, so the length 3 beats 2 and the value becomes 1. The last run is the single 2, which is length 1 and does not beat 3. The output is longest-run 3 1.

The inner loop checks j < n before it reads r[j]. Swapping the two tests would read past the end of the vector on the last run, which is undefined behaviour. Keep the bounds test first, and always put the test that protects an index before the test that reads it.

Step 3: the pair count

The pair count is the nested-loop pattern from the nested loops lesson. The outer loop picks the first position a, and the inner loop starts at a + 1 and checks each later position b. That pairs each position with each later position, so every pair is counted exactly once. Counting pairs of equal values works the same way, because the positions are different even when the values match.

Run this program with Example 3, which has eight readings to pair up. Type 8, then 120 340 340 340 9 -51 0 120, then 120, each on its own line in the Input box:

The output is:

pairs 2

The two pairs are positions (0, 6) and (6, 7). Check them against the list: the reading at position 0 is 120, and the reading at position 6 is 0, which sum to 120. The reading at position 6 is 0, and the reading at position 7 is 120, which also sum to 120. The reading 340 appears three times, but 340 plus any other reading in the list is not 120, so the three 340s add nothing.

A common error is to start the inner loop at 0. That counts every pair twice, once in each order, and it counts each reading paired with itself. The start at a + 1 is the fix, and it is the reason the inner loop exists in this form.

Step 4: the reversed sum

The reversed sum combines the digit pattern with the sign. Start by taking the absolute value of the sum, and remember whether it was negative. Then use a do-while loop, so a sum of 0 still produces one digit. Build the reversed number with rev = rev * 10 + t % 10, and remove the digit with t /= 10. At the end, put the sign back if the total was negative.

Run this program with Example 2, whose total is negative. Type 4, then -7 -7 0 10, then 10, each on its own line:

The output is:

reversed-sum -4

The total is -4. The program remembers that it was negative, works on the absolute value 4, reverses it to 4, and then applies the sign again to get -4. Try a total of 0 to check that the do-while form prints 0. A while loop would print nothing useful for 0, because its body would never run.

The reverse loop uses t > 0 as its test, and it works on a copy t. The total sum is still needed later if the program prints it, so the copy protects it. This is the same habit as the palindrome check in the classic problems lesson.

Putting it together

Your final program is the four steps combined into one. Read the input once, at the top. Then compute the count, sum, longest run, pair count and reversed sum, in that order, and print the five lines. Keep each part in its own clearly marked block, with a comment that names the pattern, so a reader can see the structure at a glance.

Test the final program with all three examples, then with the edge cases from the list. If a line is wrong, return to the step that produces it, and trace the loop on paper with a small input.

Hints

Use the hints one at a time. Try the step yourself before you open the next one.

Reference solution

Try the assignment yourself before you open this. The solution below is complete, and it passes all three examples and the edge cases above.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    // Read the input: n, then n readings, then the target.
    int n;
    cin >> n;
    vector<long long> r(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }
    long long target;
    cin >> target;
 
    // 1. Count.
    cout << "count " << n << endl;
 
    // 2. Sum: a running total that starts at 0.
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += r[i];
    }
    cout << "sum " << sum << endl;
 
    // 3. Longest run of equal neighbours. The first longest run wins ties.
    int bestLen = 0;
    long long bestVal = r[0];
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && r[j] == r[i]) {
            j++;
        }
        if (j - i > bestLen) {
            bestLen = j - i;
            bestVal = r[i];
        }
        i = j;
    }
    cout << "longest-run " << bestLen << " " << bestVal << endl;
 
    // 4. Pairs (a, b) with a < b whose readings add up to the target.
    long long pairs = 0;
    for (int a = 0; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            if (r[a] + r[b] == target) {
                pairs++;
            }
        }
    }
    cout << "pairs " << pairs << endl;
 
    // 5. Reverse the digits of |sum| and put the sign back.
    bool negative = sum < 0;
    long long t = negative ? -sum : sum;
    long long rev = 0;
    do {
        rev = rev * 10 + t % 10;
        t /= 10;
    } while (t > 0);
    if (negative) {
        rev = -rev;
    }
    cout << "reversed-sum " << rev << endl;
    return 0;
}

Stretch extension (optional)

If you finish early and want more practice, extend the program in two ways. First, sort a copy of the readings with bubble sort, using a swapped flag to stop early, and then count the pairs that add up to the target with the two-pointer method from the classic problems lesson. Check that your fast count matches the nested-loop count on every input you try. Second, read a list of query values after the target, and for each query print the first position in the sorted copy whose value is at least that query, using the lower-bound binary search from the classic problems lesson.

Write the extension as a separate program, so the five-line report still works unchanged. Note the time and space cost of each part in a comment, because an interviewer will ask for them.

Summary of this module

• A while loop repeats while its condition holds, so its body must change something the condition uses. Use it when the number of passes is not known in advance, such as reading until a sentinel.
• A for loop puts the start, the test and the update on one line. The pattern for (int i = 0; i < n; i++) runs exactly n times. Use it when you count through a range or walk an array.
• A do-while loop runs its body at least once, which suits input checks and digit counting that must handle 0.
• break leaves the innermost loop at once, and continue skips to the next pass. In a while loop, check that the update runs before any continue.
• Nested loops multiply the work. Two loops over n items cost O(n squared). Starting the inner loop at i + 1 lists each pair once.
• The classic patterns are digit peeling, the factorial and Fibonacci running values, the sieve, Euclid's method for the GCD, two pointers on a sorted array and the binary search for the first position at or above a value. Each has a known time and space cost, and you should be able to state it.
• Test the edges of every loop: zero, one, empty input, negative values and the largest value the type can hold.