Compressed ranges · Coding Gym

Solutions

To solve this problem, we know the input is already sorted and contains unique integers. The goal is to identify groups of consecutive numbers and represent each of those groups as a range, while leaving non-consecutive numbers as-is.

As we scan through the list, we track where each group of consecutive numbers starts. When we find a break (where the current number isn’t one more than the previous) we know the group has ended. If the start and end of the group are the same, it’s a single number; otherwise, we format it as a range using start->end.

This is a linear solution.

In C++, we can find the break by using adjacent_find. This is a possible solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


int main()
{
    int n; cin >> n;
    vector<int> nums(n);
    copy_n(istream_iterator<int>(cin), n, begin(nums));
    
    auto it = begin(nums);
    while (it != end(nums))
    {
        const auto groupIt = adjacent_find(it, end(nums), [](auto i, auto j){
            return j-i != 1;
        });

        cout << *it;
        if (groupIt != end(nums))
        {
            if (it != groupIt)
            {
                cout << "->" << *groupIt;
            }
        }
        else if (distance(it, groupIt) > 1)
        {
            cout << "->" << *prev(groupIt);
        }
        it = groupIt != end(nums) ? next(groupIt) : groupIt;
        cout << " ";
    }    
}

Here is a Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


def compress_ranges(nums):
    if not nums:
        return

    start = nums[0]

    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1] + 1:
            end = nums[i - 1]
            if start == end:
                print(f"{start}", end=" ")
            else:
                print(f"{start}->{end}", end=" ")
            start = nums[i]

    # last range
    end = nums[-1]
    if start == end:
        print(f"{start}")
    else:
        print(f"{start}->{end}")

Playing with patterns

This problem is a great chance to apply functional programming ideas. The core task is to group together consecutive numbers: numbers that follow each other without gaps.

Many languages and libraries offer constructs for this kind of grouping: in Python, there’s groupby; in C++, chunk_by (from ranges); and in C#’s LINQ, GroupBy. While the syntax differs, the idea is the same: collect adjacent elements as long as a condition holds.

In our case, the condition is simple: the difference between two adjacent numbers should be 1. Once we’ve built these groups, we format each one:

if the group has a single number, we print it as-is.
if it has multiple numbers, we print it as first->last, representing the full range.

This C++ solution is based on ranges and std::print (from C++23):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


auto groups = views::chunk_by(v, [](auto i, auto j){
    return j - i == 1;
}) | views::transform([](auto rng) -> std::string {
    return to_string(rng.front()) + (size(rng) > 1 ? "->" + to_string(rng.back()) : "");
});

for (auto rng : groups)
{
    print("{}, ", rng);
}

This is convenient if each group need to be processed somehow and not just printed.

Bear in mind that print can make the work already, but the format required from the problem does not match:

1
2
3
4
5


print("{}", views::chunk_by(v, [](auto i, auto j){
        return j - i == 1;
}) | views::transform([](auto rng) -> std::string {
    return to_string(rng.front()) + (size(rng) > 1 ? "->" + to_string(rng.back()) : "");
}));

Here is another version that just prints each chunk:

1
2
3
4
5
6
7
8


ranges::for_each(views::chunk_by(v, [](auto i, auto j){
    return j - i == 1;
}), [](auto rng) {
    std::print("{}", rng.front());
    if (size(rng) > 1)
        std::print("->{}", rng.back());
    print(" ");
});

A functional-style Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


from itertools import groupby
from operator import itemgetter

def compress_ranges(nums):
    if not nums:
        return ""

    groups = groupby(enumerate(nums), key=lambda x: x[1] - x[0])
    to_range = lambda g: f"{g[0]}" if len(g) == 1 else f"{g[0]}->{g[-1]}"

    return " ".join(map(
            lambda g: to_range(list(map(itemgetter(1), g[1]))),
            groups)
    )

_ = input()
nums = map(int, input().split())
print(compress_ranges(nums))

A LINQ-based approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
    static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());
        int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);

        var out = nums
            .Select((x, index) => new { Rank = x - index, Value = x })
            .GroupBy(x => x.Rank)
            .Select(x => new { Min = x.Min(y => y.Value), Max = x.Max(y => y.Value)})
            .Select(x => x.Min == x.Max ? $"{x.Min} " : $"{x.Min}->{x.Max} ")
            .ToList();
        
        out.ForEach(Console.Write);
    }
}