form a number using consecutive numbers

Question

I was puzzled with one of the question in Microsoft interview which is as given below:

A function should accept a range( 3 - 21 ) and it should print all the consecutive numbers combinations to form each number as given below:

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

could you please help me in forming this sequence in C#?

Thanks, Mahesh

Answer 1

So here is a straightforward/naive answer (in C++, and not tested; but you should be able to translate). It uses the fact that

1 + 2 + ... + n = n(n+1)/2,

which you have probably seen before. There are lots of easy optimisations that can be made here which I have omitted for clarity.

---

void WriteAsSums (int n)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = i; j < n; j++)
    {
      if (n = (j * (j+1) - i * (i+1))/2) // then n = (i+1) + (i+2) + ... + (j-1) + j
      {
        std::cout << n << " = ";
        for (int k = i + 1; k <= j; k++)
        {
          std::cout << k;
          if (k != j) // this is not the interesting bit
            std::cout << std::endl;
          else
            std::cout << " + ";
        }
      }
    }
  }
}

Answer 2

This is some pseudo code to find all the combinations if any exists:

function consecutive_numbers(n, m)
    list = [] // empty list
    list.push_back(m)
    while m != n
        if m > n
            first = list.remove_first
            m -= first
        else
            last = list.last_element
            if last <= 1
                return [] 
            end
            list.push_back(last - 1) 
            m += last - 1
        end
    end
    return list
end

function all_consecutive_numbers(n)
    m = n / 2 + 1
    a = consecutive_numbers(n, m)
    while a != []
        print_combination(n, a)
        m = a.first - 1
        a = consecutive_numbers(n, m)
    end
end

function print_combination(n, a)
    print(n + " = ")
    print(a.remove_first)
    foreach element in a
        print(" + " + element)
    end
    print("\n")
end

A call to all_consecutive_numbers(21) would print:

21 = 11 + 10
21 = 8 + 7 + 6
21 = 6 + 5 + 4 + 3 + 2 + 1

I tested it in ruby (code here) and it seems to work. I'm sure the basic idea could easily be implemented in C# as well.