algorithm - How to find a maximal odd decomposition of integer M? -

let m integer in range [1; 1,000,000,000].

a decomposition of m set of unique integers sum equal m.

a decomposition odd if contains odd integers.

a decomposition of m maximal if there no other decomposition of m greater in size of set.

write function:

int[] maxodddecomposition(int m) 

that returns array maximal odd decomposition of m. numbers in array should in ascending order. if m not have odd decomposition, array should empty. if there more 1 correct answer, function may return of them.

for example, m = 6 has 4 decompositions:

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

only 1 + 5 odd decomposition, maximal odd decomposition. should return in array such array[0] = 1 , array[1] = 5.

expected worst-case time , space complexity o(sqrt(m)).

---

what i've tried:

since time complexity has sqrt(m) reminded me of naive factorization of m algorithm, iterate 1 sqrt(m). no further thoughts appeared though. must fast, sqrt(m) steps.

so, did examples. how find answer 20 example? odd numbers less 20? 1 + 3 + 5 + 7 + ... have 16. so, add 4, 4 even.

so, let's replace 7 (7 + 4) = 11 , done: 1 + 3 + 5 + 11. noticed initial sequence had floor(sqrt(m)) elements, perfect. let's code in pseudo-code:

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

i did special case m = 2, returning empty array. thought that's it, finito.

i didn't notice breaks 3, because gives 1 + 2 instead of 3. , 5, gives 1 + 3 + 1, instead of 5. , many more.

---

how solve it?

here deterministic solution problem. suppose m = {1, 3, 5, ..., 2*k-3, 2*k-1, r} r <= 2*k + 1. 'obvious' maximal decomposition not going have more numbers (k+1).

we have following cases k > 3 (the reasoning , handling of earlier cases presented later):

case 1. if r odd , equal 2*k+1: add r list thereby giving decomposition of (k+1) elements.

case 2. if r even: replace {(2*k-1), r} {2*k-1+r} giving decomposition of k elements.

case 3. if r odd , not equal 2*k+1: replace first , last 2 elements in series {1, 2*k-1, r} {2*k+r} giving decomposition of (k-1) elements.

note worst case of (k-1) elements occur when input of form n^2 + (odd number < 2*k+1).

also note (case 3) break in case number of elements less 3. example, decomposition of 5 , 7. have special-case these numbers. likewise (case 2) break 3 , have special-cased. there no solution m=2. hence restriction k > 3 above. 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;     (int = 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;     }      (int = start; < count; i++) {         printf("%d\n", arr[i]);     }      return 0; } 

example:

enter m:24 array is: 1 3 5 15  enter m:23 array is: 3 5 15