How to find the maximum odd expansion of an integer M?

Question

Let M be an integer in the range [1; 1 billion].

The decomposition of M is a set of unique integers whose sum is M.

The decomposition is odd if it contains only odd integers.

The decomposition of M is maximal if the other decomposition of M is larger in size of the set.

Write a function:

int[] maxOddDecomposition(int M) 

which returns an array with maximum odd decomposition M. The numbers in the array must be in ascending order. If M has no odd decomposition, the array must be empty. If there is more than one correct answer, the function can 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, so this is the maximum odd decomposition. We must return it to the array so that array[0] = 1 and array[1] = 5 .

The expected worst case time and space complexity is O (sqrt (M)).

---

What I tried:

Since the time complexity should be sqrt (M), it reminded me of the naive factorization of the algorithm M, where we repeat from 1 to sqrt (M). However, no further thoughts appeared. Only it should be very fast, only sqrt (M) steps.

So, I made some examples. How to find the answer to 20, for example? What are odd numbers less than 20? 1 + 3 + 5 + 7 + ... we already have 16. So we could add 4, but 4 are even.

So, replace 7 with (7 + 4) = 11, and we will do the following: 1 + 3 + 5 + 11. I noticed that the original sequence always had floor elements (sqrt (M)) perfect. Let the code in pseudocode:

 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 made a special case for M = 2, returning an empty array. I thought it was, finito.

I did not notice that it splits into 3 because it gives 1 + 2 instead of 3 . And for 5 it gives 1 + 3 + 1 instead of 5 . And for many more.

---

How would you allow it?

Answer 1

This is a deterministic solution to the problem. Suppose that M = {1, 3, 5, ..., 2 * k-3, 2 * k-1, r}, where r <= 2 * k + 1. Obviously, the maximum decomposition will not have more numbers than (k + 1).

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

Case 1. If r is odd and equals 2 * k + 1: add r to the list, thereby giving an expansion of the elements (k + 1).

Case 2. If r is even: replace {(2 * k-1), r} with {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 last two elements in the series {1, 2 * k-1, r} with {2 * k + r} giving a decomposition of (k-1) elements .

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

Also note that (Case 3) will break if the number of elements is less than 3. For example, decomposition 5 and 7. We will have a special case of these numbers. In the same way (case 2) it will break by 3 and will have a special cover. For M = 2, there is no solution. Therefore, the restriction k> 3 is higher. Everything else should work fine.

It takes O(sqrt(M)) .

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 

Answer 2

Here is an idea that should work. This requires a clean removal of no more than 1 number from the greedy set that you create.

Create your O (sqrt (M)) list as usual (without result[len - 1] = M - sum; ). If the sum is not a square number (i.e.):

• Add the following larger odd number

• Take the difference between your amount and target number → N

  • If N is odd, remove the corresponding number
  • If N is equal but not 2, remove the largest odd number less than N, and 1
  • If N is 2, delete the penultimate number that you just added. It will have a value of 0

Evidence:

• If you consistently add consecutive odd numbers, the list should be as dense as possible, i.e. you cannot have a larger list
• Also, the difference is always limited to the odd number that you add in step 2, so a clean deletion of up to two numbers is always an account of odd or even differences.

Examples:

• Suppose you want 42: build [1, 3, 5, 7, 9, 11], add 13 => sum = 49, delete 7 (without deleting the network)
• You want 39: build [1, 3, 5, 7, 9, 11], add 13, delete 1 and 9 (clean delete 1)
• You want 38: build [1, 3, 5, 7, 9, 11], add 13, delete 11 (no blank paragraphs)

EDIT: the error in the latter case is fixed given @ user1952500

Answer 3

I don’t understand why people have to make it so complicated. Odd decomposition is similar to the self-conjugate section expanded on its side and expanded, for example n = 13

 4 4 3 2 => => => 7 5 1 xxxx rotate x unfold out xxxxxxx xxxx clockwise ↖ xx ↗ each side xxxxx xxx 45 degrees xxx => x xxxxxxxxx 

The larger the odd decomposition, the greater the “bounding square” of the corresponding self-adjoint. By "bounding box" I mean the square of the upper left corner, which is a constant in all odd expansions of a similar size. For example, we could write 13 as self-adjoint {5,3,3,1,1} , and the 9-element “bounding box” would remain the same, with the corresponding odd decomposition {9,3,1} :

 5 3 3 1 1 => 9 3 1 xxxxxxxxxxxxxx xxxxxx xxxx x x 

To get an odd decomposition with the greatest power, find the largest “bounding box” with an 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 displays all the possibilities:

 fm = 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]]