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

if we slice a into 2 digit, then a = b + (b+1) = 2*b + (0+1)
if we slice a into 3 digit, then a = b + (b+1) + (b+2) = 3*b + (0+1+2)
...
if we slice a into n digit, then a = b + (b+1) +...+ (b+n) = nb + (0+1+n-1)
the last result is a = nb + n*(n-1)/2, a,b,n are all ints.
so O(N) Algorithm is:

void seq_sum(int a)
{
// start from 2 digits
   int n=2;
   while(1)
   {
      int value = a-n*(n-1)/2;
      if(value < 0)
         break;
// meet the quotation we deduct
      if( value%n == 0 )
      {
           int b=value/n;
// omit the print stage
           print("......");
      }
      n++;
   }
}

Answer 2

Here's something in Groovy, you should be able to understand what's going on. It's not the most efficient code and doesn't create the answers in the order you cite in your question (you seem to be missing some though) but it might give you a start.

def f(a,b) {

  for (i in a..b) {

    for (j in 1..i/2) {

      def (sum, str, k) = [ 0, "", j ]

      while (sum < i) {
        sum += k
        str += "+$k"
        k++
      }

      if (sum == i) println "$i=${str[1..-1]}"
     }
  }
}

Output for f(3,21) is:

3=1+2
5=2+3
6=1+2+3
7=3+4
9=2+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
15=4+5+6
15=7+8
17=8+9
18=3+4+5+6
18=5+6+7
19=9+10
20=2+3+4+5+6
21=1+2+3+4+5+6
21=6+7+8
21=10+11

Hope this helps. It kind of conforms to the tenet of doing the simplest thing that could possibly work.

Answer 3

I like this problem. Here is a slick and slightly mysterious O(n) solution:

void DisplaySum (int n, int a, int b)
{
  std::cout << n << " = ";
  for (int i = a; i < b; i++) std::cout << i << " + ";
  std::cout << b;
}

void WriteAsSums (int n)
{
  N = 2*n;

  for (int i = 1; i < N; i++)
  {
    if (~(N%i))
    {
      int j = N/i;
      if (j+i%2)
      {
        int a = (j+i-1)/2;
        int b = (j-i+1)/2;
        if (a>0 & a<b) // exclude trivial & negative solutions
          DisplaySum(n,a,b);
      }
    }
  }
}

Answer 4

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.

Answer 5

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 << " + ";
        }
      }
    }
  }
}