Display 1,2,3,4,5,6,8,10,11 as 1-6,8,10-11

Question

I have this sequence 1,2,3,4,5,6,8,10,11

Expected output is 1-6,8,10-11

This problem is about formatting the sequence in easy readable form

I tried with c# and used many if & else.

Interviewer said, there is some simple algorithm to do this.

I have no idea how to achive this very simple.

Also for 1,2,3 i shown 1-3. They said its wrong!.

Is there any design pattern(interpreter) involved in this logic?

Solution 1

Here is one way of doing it:

        int[] numbers = { 1, 2, 3, 4, 5, 6, 8, 10, 11 };

        int start, end;
        for (int i = 0; i < numbers.Length; i++)
        {
            start = numbers[i];

            while (i < numbers.Length - 1 && numbers[i] + 1 == numbers[i + 1])
                i++;

            end = numbers[i];

            if(start == end)
                Console.WriteLine(start);
            else
                Console.WriteLine(start + " - " + end);
        }

This will display subsequent numbers that grow incrementally as range. Numbers that are not increasing linearly are not written as part of a range.

Here is another version of the first approach, it utilizes the same for loop to iterate on range:

        int temp = numbers[0], start, end;
        for (int i = 0; i < numbers.Length; i++)
        {
            start = temp;

            if (i < numbers.Length - 1 )
                // if subsequent numbers are incremental loop further
                if (numbers[i] + 1 == numbers[i + 1])
                    continue;
                // if they are not, number at index i + 1 is a new 'start' for the next iteration
                else
                    temp = numbers[i + 1];

            end = numbers[i];

            if (start == end)
                Console.WriteLine(start);
            else
                Console.WriteLine(start + " - " + end);
        }

Solution 2

A simple implementation in C# could look like this:

public string Format(IEnumerable<int> input)
{
    var result = string.Empty;

    var previous = -1;
    var start = -1;
    var first = true;

    foreach(var i in input)
    {
        if(start == -1)
            start = i;
        else if(previous + 1 != i)
        {
            result += FormatRange(start, previous, first);
            first = false;
            start = i;
        }

        previous = i;
    }

    if(start != -1)
        result += FormatRange(start, previous, first);

    return result;
}

public string FormatRange(int start, int end, bool isFirst)
{
    var result = string.Empty;
    if(!isFirst)
        result += ", ";
    if(start == end)
        result += start;
    else
        result += string.Format("{0}-{1}", start, end);
    return result;
}

This will also output 1-3 for the input 1,2,3, which is perfectly valid. Without a specification what the output should be instead it's impossible to answer that part.

Solution 3

Probably not a suitable answer for an interview question, but using LINQ is another way to solve this.

int[] numbers = { 1, 2, 3, 4, 5, 6, 8, 10, 11 };
var remains = numbers.AsEnumerable();

while (remains.Any())
{
    int first = remains.First();
    int last = remains.TakeWhile((x, i) => x - first == i).Last();
    remains = remains.Skip(last - first + 1);
    Console.Write(first + (first == last ? "" : "-" + last) + (remains.Any() ? "," : Environment.NewLine));
}

Solution 4

Heres my best attempt. Not clever, but simple enough to satisfy that requirement I believe. I'm still pretty confused as to why "1-3" was wrong though....

    var numbers = new int[] { 1, 2, 3, 4, 5, 6, 8, 10, 11, 12 };

    var groups = new Dictionary<int, int>();
    groups.Add(numbers.First(), numbers.First());

    foreach (var num in numbers.Skip(1))
    {
        var grp = groups.Last();
        if (grp.Value + 1 == num)
        {
            groups[grp.Key] = num;
        }
        else
        {
            groups.Add(num, num);
        }
    }

    var output = string.Join(",", groups.Select(grp => (grp.Key == grp.Value) ? grp.Value.ToString() : grp.Key.ToString() + "-" + grp.Value.ToString()));

Note: of course using the dictionary and linq etc is completely unnecessary (and way too specific for an answer requiring an algorithm), but I thought it highlighted the grouping aspect of the problem nicely

Solution 5

The following groups consecutive integers, and outputs a string for each group. However, it also allows you to specify the minimum length of group which you want to hyphenate; anything less will just give you the individual numbers. Thus if you only want to hyphenate groups of 4 or more, you can pass in 4; if you want to hyphenate pairs, you can pass in 2. (I'd want to use 3 myself, but I can't tell what they want.)

It also doesn't keep any collections of numbers as it goes along, because you don't need to.

Method:

static IEnumerable<string> Group(IEnumerable<int> input, int minLength)
{
    int currentStart = int.MinValue;
    int currentLength = 0;
    foreach (int c in input)
    {
        if (currentLength > 0)
            if (currentStart + currentLength == c)
                currentLength++;
            else
            {
                if (currentLength >= minLength)
                    yield return string.Format("{0}-{1}",
                        currentStart, currentStart + currentLength - 1);
                else
                    for (int i = currentStart; i < currentStart + currentLength; i++)
                        yield return i.ToString();
                currentStart = c;
                currentLength = 1;
            }
        else
        {
            currentStart = c;
            currentLength = 1;
        }
    }
    if (currentLength >= minLength)
        yield return string.Format("{0}-{1}",
            currentStart, currentStart + currentLength + 1);
    else
        for (int i = currentStart; i < currentStart + currentLength; i++)
            yield return i.ToString();
}

Usage:

int minCount = 3;
int[] input = new[] { 1, 2, 3, 4, 5, 6, 8, 10, 11 };
Console.WriteLine(String.Join(",", Group(input, minCount)));

View more solutions

Comments

[Bernhard Barker]

Good answer, but I think the point (as least of the interview question) was to find a simple algorithm, not to 'cheat' by using APIs.

[Daniel Hilgarth]

@Dukeling: Identifying the ranges is done using a simple algorithm.

[Daniel Hilgarth]

@Dukeling: But I changed it anyway to not use LINQ for the output.

[Billa]

I dont see the first number in the format. It shows -5 instead of 1-5

[Shivam]

@BadDeveloper First line of code prints first element. May be you missed it!

[Billa]

This logic seems pretty simple to me :)

[Ivan Golović]

I agree, the logic and implementation are quite simple:)

[Adrian Marinica]

This is the neatest version here.

[Servy]

Note that this is iterating the source sequence many times, which is not suitable for arbitrary enumerables, even if it works fine for an array.

[Xavier]

@IvanG Can the reverse be possible? if the user inputs as 10,1-4,5-8, 9 the output should be 1,2,3,4,5,6,7,8,9,10