KiraAvi's blog

Odd decomposition of a number
By KiraAvi, history, 5 years ago, In English

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.

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

What is the problem source?

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Not sure, but I think placing consecutive odd numbers starting from 1 except the last one, will always give optimal ans.

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    That is definitely the answer because you're maximizing the ammount of numbers in the set, but you would need to see the case where you would need to merge the last two elements in the set (for example, for m = 10 you would innitially have {1,3,5} but the only way to reach an answer is by making a set of size 2 like {1,9}).

    → Reply
»
5 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

The smallest number that can be formed by adding $$$k$$$ odd distinct numbers is $$$\displaystyle\sum_{i=1}^k (2i-1) = k^2$$$. Hence, $$$ans(M) \le \sqrt{M}$$$, where $$$ans(M)$$$ is the length of a maximal odd decomposition of $$$M$$$.

Now, let's add the first $$$k = \lfloor\sqrt{M}\rfloor$$$ odd numbers, and that sum is equal to $$$k^2 \le M$$$; then, there are two cases:

  • $$$M - k^2$$$ is even. Then we can add $$$M - k^2$$$ to the biggest chosen number. That would keep every chosen number as odd, and the total sum equal to $$$M$$$. In this case the array would be
$$$[1, 3, 5, \dots, 2(k-1) - 1, 2k - 1 + (M - k^2)]$$$
  • $M - k^2$ is odd. That means that we need to add either a new odd number (which is impossible, because then the sum would be become greater than $$$M$$$) or add an odd amount to some of the chosen numbers (which is also impossible, because then one of the numbers would become even). Therefore, we cannot take $$$k$$$ numbers, so let's try with the first $$$k - 1$$$ odd numbers; their sum is $$$(k - 1)^2$$$, which has different parity as $$$k^2$$$, therefore $$$M - (k-1)^2$$$ is even, which means that we can add $$$M - (k - 1)^2$$$ to the biggest chosen number ($$$k - 1$$$), and get sum $$$M$$$ while keeping the $$$k - 1$$$ chosen numbers odd. In this case the array would be:
$$$[1, 3, 5, \dots, 2(k-1) - 1 + (M - (k-1)^2]$$$
→ Reply
»
5 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Explained here: https://stackoverflow.com/questions/31277297/how-to-find-a-maximal-odd-decomposition-of-integer-m

→ Reply