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?
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