title: How to find a maximal odd decomposition of integer M?
body: <p>Let M be an integer in range [1; 1,000,000,000].</p>
  
  <p>A <em>decomposition</em> of M is a set of unique integers whose sum is equal to M. </p>
  
  <p>A decomposition is <em>odd</em> if it contains only odd integers.</p>
  
  <p>A decomposition of M is <em>maximal</em> if there is no other decomposition of M greater in size of the set.</p>
  
  <p>Write a function:</p>
  
  <pre><code>int[] maxOddDecomposition(int M)
  </code></pre>
  
  <p>that returns an array with a <em>maximal odd decomposition</em> of M. The numbers in array should be in ascending order. If M does not have any odd decomposition, an array should be empty. If there is more than one correct answer, the function may return any of them.</p>
  
  <p>For example, M = 6 has four decompositions:</p>
  
  <pre><code>6 = 1 + 2 + 3
    = 1 + 5
    = 2 + 4
    = 6
  </code></pre>
  
  <p>Only <code>1 + 5</code> is an odd decomposition, thus is the maximal odd decomposition. We should return it in array such that <code>array[0] = 1</code> and <code>array[1] = 5</code>.</p>
  
  <p>Expected worst-case time and space complexity is O(sqrt(M)).</p>
  
  <hr>
  
  <p>What I've tried:</p>
  
  <p>Since the time complexity has to be sqrt(M) it reminded me of naive factorization of M algorithm, where we iterate from 1 to sqrt(M). No further thoughts appeared though. Only that it must be really fast, only sqrt(M) steps.</p>
  
  <p>So, I did some examples. How to find an answer for 20 for example? What are the odd numbers less than 20? 1 + 3 + 5 + 7 + ... we already have 16. So, we could add 4, but 4 is even. </p>
  
  <p>So, let's replace 7 with (7 + 4) = 11 and we are done: 1 + 3 + 5 + 11. What I noticed is that the initial sequence had always floor(sqrt(M)) elements, perfect. Let's code it up in pseudo-code:</p>
  
  <pre><code>int len = floor(sqrt(M));
  int result[] = new int[len];
  int sum = 0;
  for (i = 0; i &lt; len - 1; i++) {
      result[i] = 1 + 2*i;
      sum += result[i];
  }
  result[len - 1] = M - sum;
  return result;
  </code></pre>
  
  <p>I did a special case for M = 2, returning an empty array. I thought that's it, finito.</p>
  
  <p>I didn't notice that it breaks for 3, because it gives <code>1 + 2</code> instead of <code>3</code>. And for 5, gives <code>1 + 3 + 1</code>, instead of <code>5</code>. And for many more.</p>
  
  <hr>
  
  <p>How would you solve it?</p>