How to find a maximal odd decomposition of integer M?

Question

Let M be an integer in range [1; 1,000,000,000].

A decomposition of M is a set of unique integers whose sum is equal to M.

A decomposition is odd if it contains only odd integers.

A decomposition of M is maximal if there is no other decomposition of M greater in size of the set.

Write a function:

int[] maxOddDecomposition(int M)

that returns an array with a maximal odd decomposition 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.

For example, M = 6 has four decompositions:

6 = 1 + 2 + 3
  = 1 + 5
  = 2 + 4
  = 6

Only 1 + 5 is an odd decomposition, thus is the maximal odd decomposition. We should return it in array such that array[0] = 1 and array[1] = 5.

Expected worst-case time and space complexity is O(sqrt(M)).

---

What I've tried:

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.

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.

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:

int len = floor(sqrt(M));
int result[] = new int[len];
int sum = 0;
for (i = 0; i < len - 1; i++) {
    result[i] = 1 + 2*i;
    sum += result[i];
}
result[len - 1] = M - sum;
return result;

I did a special case for M = 2, returning an empty array. I thought that's it, finito.

I didn't notice that it breaks for 3, because it gives 1 + 2 instead of 3. And for 5, gives 1 + 3 + 1, instead of 5. And for many more.

---

How would you solve it?

Answer 1

I don't see why people have to make it so complicated. An odd decomposition is like a self-conjugate partition turned on its side and unfolded out, for example, n = 13

4 4 3 2     =>              =>            =>              7 5 1

x x x x   rotate             x         unfold out      x x x x x x x
x x x x   clockwise     ↖  x  x  ↗      each side       x x x x x
x x x     45 degrees      x  x  x           =>               x
x x                      x  x  x  x 
                          x  x  x

The larger an odd decomposition is, the larger the "bounding-square" of the corresponding self-conjugate. By "bounding-square" I mean the top left corner square, which is a constant in all similar-sized odd decompositions. For example, we could have written 13 as the self-conjugate {5,3,3,1,1} and the 9-cell "bounding square" would remain the same, with corresponding odd decomposition {9,3,1}:

5 3 3 1 1        =>            9 3 1

x x x x x                x x x x x x x x x
x x x                          x x x
x x x                            x
x
x

To get the odd decomposition with the largest cardinality, find the largest "bounding square" with even remainder.

Example:

M = 24

Bounding square | remainder
1                 23 
4                 20
9                 15
16                8
25...too large

Place the remainder in any diagonally-symmetric way you like. The simplest way might be

xxxx         xxxxxxxx
xxxx   =>    xxxx
xxxx         xxxx
xxxx         xxxx
             x
             x
             x
             x

Decompose: 15,5,3,1

I think this Haskell code outputs all possibilities:

f m = g [1,3..bestRoot*2 - 1] remainder 0 []
  where root = floor (sqrt (fromIntegral m))
        bestRoot = head $ dropWhile (\x -> odd (m - x^2)) [root,root - 1..1]
        remainder = m - bestRoot^2
        g (x:xs) r prev res
          | null xs   = [reverse ((x + r):res)]
          | otherwise = do r' <- takeWhile (<= div remainder bestRoot) [prev,prev + 2..]
                           g xs (r - r') r' ((x + r'):res)

Output:

*Main> f 24
[[1,3,5,15],[1,3,7,13],[1,5,7,11],[3,5,7,9]]

*Main> f 23
[[1,3,19],[1,5,17],[1,7,15],[3,5,15],[3,7,13],[5,7,11]]

*Main> f 38
[[1,3,5,7,9,13]]

*Main> f 37
[[1,3,5,7,21],[1,3,5,9,19],[1,3,7,9,17],[1,5,7,9,15],[3,5,7,9,13]]

*Main> f 100
[[1,3,5,7,9,11,13,15,17,19]]

Answer 2

Here is a deterministic solution to the problem. Suppose M = {1, 3, 5, ..., 2*k-3, 2*k-1, r} where r <= 2*k + 1. It is 'obvious' that the maximal decomposition is not going to have more numbers than (k+1).

We have the following cases for k > 3 (the reasoning and handling of earlier cases is presented later):

Case 1. If r is odd and equal to 2*k+1: add r into the list thereby giving a decomposition of (k+1) elements.

Case 2. If r is even: replace {(2*k-1), r} by {2*k-1+r} giving a decomposition of k elements.

Case 3. If r is odd and not equal to 2*k+1: replace the first and the last two elements in the series {1, 2*k-1, r} by {2*k+r} giving a decomposition of (k-1) elements.

Note that the worst case of (k-1) elements will occur when the input is of the form n^2 + (odd number < 2*k+1).

Also note that (Case 3) will break in case the number of elements is less than 3. For example, the decomposition of 5 and 7. We will have to special-case these numbers. Likewise (Case 2) will break for 3 and will have to be special-cased. There is no solution for M=2. Hence the restriction k > 3 above. Everything else should work fine.

This takes O(sqrt(M)) steps.

Some C/C++ code:

#include <stdio.h>

int main(int argc, char *argv[])
{
    printf("Enter M:");
    int m = 0;
    scanf("%d", &m);

    int arr[100] = {0};
    printf("The array is:\n");
    switch(m) {
        case 2:
            printf("No solution\n");
            return 0;
        case 1:
        case 3:
        case 5:
        case 7:
            printf("%d\n", m);
            return 0;
    }

    int sum = 0;
    int count = 0;
    for (int i = 1; (sum + i) < m; i+= 2) {
        arr[count++] = i;
        sum += i;
    }
    int start = 0;
    int r = m - sum;
    if (r % 2 == 0) {
        arr[count - 1] += r;
    } else if (r > arr[count - 1]) {
        arr[count++] = r;
    } else {
        start = 1;
        arr[count - 1] += r + 1;
    }

    for (int i = start; i < count; i++) {
        printf("%d\n", arr[i]);
    }

    return 0;
}

Example:

Enter M:24
The array is:
1
3
5
15

Enter M:23
The array is:
3
5
15