[C++] Math Solution Explained Step-by-step, 100% Time, ~70% Space
Nice math challenge we have here :)\n\nOkay, let\'s proceed step by step and see if we can spot on how we can figure out the amount of needed operations.\n\nFor
Nice math challenge we have here :)\n\nOkay, let\'s proceed step by step and see if we can spot on how we can figure out the amount of needed operations.\n\nFor example, let\'s assume we start with `n == 6` and let\'s do some grouping on the series with the first `6` odd numbers, like this:\n\n```cpp\n//    1,     3,     5,     7,     9,    11 == \n//    1,     3,     5, 6 + 1, 6 + 3, 6 + 5 ==\n// 1+ 5, 3 + 3, 5 + 1,     6,     6,     6 ==\n//    6,     6,     6,     6,     6,     6\n```\n\nBasically we can proceed removing values from the second half so that they mirror what is in the first half in order to balance every series we need to balance.\n\nOr, more simply, the number of operations needed is going to be equal to the sum of all the elements in the first half.\n\nLet\'s move on from there and try to figure out how to proceed, still continuing on our example:\n\n```cpp\n//       1 +       3 +       5 ==\n// (0 + 1) + (2 + 1) + (4 + 1) ==\n// (1 + 1 + 1) + (0 + 2 + 4) ==\n// 3 + 2 * (0 + 1 + 2)\n```\n\nAnd from here we can finally derive some more general formula, calling `h` half the value of `n` and having found that our result equates to `h` plus twice the sum of all the first `h - 1` numbers; with a bit more grouping we can have:\n\n```cpp\n// h + 2 * h * (h - 1) / 2 ==\n// h + h * (h - 1) ==\n// h * h ==\n// (n / 2) * (n / 2)\n```\n\nHence our own solution is just `n * n / 4`; you might have noticed that things might change with odd numbers, but they actually do not: if we had to rebalance for, say, `n == 7`, then we would have `1, 3, 5, 7, 9, 11, 13` and we can ignore the cental element (`7`) and just rebalance the left side taking from the right exactly as we did before.\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int minOperations(int n) {\n        return n * n / 4;\n    }\n};\n```
['Math', 'C', 'C++']