Finding the sum of all the segment counts of a 7-segment display in a range

Question

I'm working on a programming challenge and the question is as follows:

Once Max found an electronic calculator from his grandfather Dovlet's chest. He noticed that the numbers were written with seven-segment indicators (https://en.wikipedia.org/wiki/Seven-segment_display).

Max starts to type all the values from a to b. After typing each number Max resets the calculator. Find the total number of segments printed on the calculator.

For example if a = 1 and b = 3 then at first the calculator will print 2 segments, then — 5 segments and at last it will print 5 segments. So the total number of printed segments is 12.

Input

The only line contains two integers a, b (1 ≤ a ≤ b ≤ 10⁶) — the first and the last number typed by Max.

Output

Print the only integer a — the total number of printed segments.

Examples

input

1 3

output

12

input

10 15

output

39

Here's my attempt:

#include <iostream>
#include <unordered_map>

static std::unordered_map<char, int>
         segment_count = {
                            {'1', 2},
                            {'2', 5},
                            {'3', 5},
                            {'4', 4},
                            {'5', 5},
                            {'6', 6},
                            {'7', 3},
                            {'8', 7},
                            {'9', 6},
                            {'0', 6}
                         };

int get_number_of_segments(char num) {
  return segment_count[num];
}

int main() {
  int start, end, sum = 0;

  std::cin >> start >> end;

  for(int i = start; i <= end; ++i) {
    std::string current_num = std::to_string(i);
    for(auto c: current_num) {
      sum += get_number_of_segments(c);
    }
  }
  std::cout << sum << '\n';
}

When I submit the code, it fails on a timeout for a test case (unknown test case). How can I make it more efficient? All tests should run in under 1 second.

One idea I've had is to store the numbers not in the "one's place" - these won't change.

For instance: in the sequence 10, 11, 12, 13, 14, ..., I don't need to lookup 1 each time. I only need to look at the last digit until I see a 9.

Perhaps there are better ways to do this, though.

Any help would be appreciated!

Answer 1

Here are some things that may help you improve your program. First, I'll mention a few things about the code you've already written, and then I'll describe an idea for a better algorithm.

Be careful with signed versus unsigned

By the problem description, neither start nor end can be less than 1, so they should probably be declared as unsigned rather than int.

Isolate calculation from I/O

The main routine does both the input and output and also is materially involved in the main calculation. I'd advocate that that function should be isolated like this:

int segcount(unsigned start, unsigned end)
{
  unsigned sum = 0;
  for(auto i = start; i <= end; ++i) {
    std::string current_num = std::to_string(i);
    for(auto c: current_num) {
      sum += get_number_of_segments(c);
    }
  }
  return sum;
}

int main() {
  unsigned start, end;

  std::cin >> start >> end;
  auto sum = segcount(start, end);
  std::cout << sum << '\n';
}

Use const where practical

The segment_count map shouldn't be changed once constructed, and so it should be declared const.

Avoid global variables

The segment_count variable is only used within get_number_of_segments(), so it should go there instead of being a global. I would also avoid the overhead of the std::unordered_map by using a simple array:

unsigned get_number_of_segments(char num) {
    static constexpr std::array<unsigned, 10> segment_count{
        6, 2, 5, 5, 4, 5, 6, 3, 7, 6
    };
    return segment_count[num-'0'];
}

A better algorithm

Your existing code, while not the fastest possible, does have a significant advantage in that it is obviously correct. We can use that to verify any alternative approach as well as using it for timing comparisons. From here to the end of this review, I'll be showing stepwise improvements in the code.

Write a test harness

We might write several versions of the code and want to compare them. One nice way to do that is using a templated structure and a macro like this:

template <typename F>
struct testfunc {
    F *fn;
    const char *name;
};

#define TEST(x) { x, #x }

Now we can easily make an array of tests and run through all alternative algorithms:

#include "stopwatch.h"
int main()
{
    const testfunc<decltype(segcount)> test[]{
        TEST(segcount),
        TEST(segcount2),
    };

    unsigned start, end, sum;

    std::cin >> start >> end;
    for (const auto t : test) {
        Stopwatch<std::chrono::milliseconds> sw;
        sum = t.fn(start, end);
        std::cout << t.name << ": " << sum << ", " << sw.stop() << "ms\n";
    }
}

Note that this uses my Stopwatch template, but one could use an alternative if desired.

Think carefully about the problem

First, let's consider a range of single digit numbers. If we go from 1 to 5, for example, we simply add up the segment counts for each of those digits \$= 2+5+5+4+5 = 21\$. For a range that doesn't start from 1, such as for 3 to 5, we can calculate it one of two ways. We could calculate just for those numbers \$= 5+4+5 = 14\$ or we could calculate 1 to 5 and subtract 1 to 2. The motivation for doing it by the latter method is that we can precalculate all possible ranges for a digit and then simply do two lookups and a subtraction.

We can now extend this to look at two-digit numbers. If we have a range in which the first digit doesn't change, such as 71 to 75 it's simply the single digit range 1 to 5 (which we already calculated above is 21) plus the size of the range (5) times the segments for the first digit (3), so the answer is \$21 + 5(3) = 36\$.

If it's a two-digit number for which the first digit does change, we can break it down into a sum of two-digit ranges for which the leading digit is constant. For example, if we go from 71 to 88, we can consider it as two subranges: 71 to 79 and 80 to 88 where the algorithm above could be applied.

I think you can probably take it from there and see how to extend the algorithm generically.