101–110 of 188 posts
Only positive integers are meant to be allowed. (Zero excluded.)
Combining is meant to work on adjacent pairs of integers.
If this is used in coding interviews, I deny any responsibility. Unless it's used in interviewing me, in which case I will totally take credit.
I hate little puzzles like this when presented in isolation, my brain just bounces off them. If the EXACT same puzzle was presented as part of a real problem with context and reasons, my brain would be all over it and I'd work out a solution. As another comment says, it will inevitably show up as a coding interview, one that I would likely fail!
The broader contexts could be this: look at this puzzle as a way for reinvent sorting as a delegation of operations (split + combine) instead of traditional "swapping" of values. As CPU arithmetic is faster then memory operations some real treasure may be hidden in this new approach.
Earlier quoted context omitted.
What do you mean by that exactly and why would it be 'dynamic programming' ?
"Dynamic programming" is jargon from competitive programming. It sounds a lot more sophisticated than it is. In reality, it is nothing more than memoization of function calls into an array.
No, it's the next step after memoization.
Recursion is the slowest approach of implementing many algorithms, as it will duplicate a lot of computation of subproblems. It solves a lot of subproblems many times.
Memoization is a cheap fix, it will not solve subproblems multiple times. It stores subproblems it has already solved, along with the solution. But it has an increasingly large state, keeping solutions of subproblems in memory which are actually no longer needed.
Dynamic programming is a manipulation on algorithms relying on memoization. It takes such an algorithm, and it makes the state as small as possible. So solutions of subproblems are discarded when they are no longer needed.
Like in memoization, dynamic programming will keep around previous subproblem solutions. But it will only keep the ones around it still needs in the future, and discard what is no longer needed. This often requires a change in representation of that state and in the order in which the subproblems are solved. But it will run much faster than recursion, on less memory than memoized approaches.
I hate little puzzles like this when presented in isolation, my brain just bounces off them. If the EXACT same puzzle was presented as part of a real problem with context and reasons, my brain would be all over it and I'd work out a solution. As another comment says, it will inevitably show up as a coding interview, one that I would likely fail!
Earlier quoted context omitted.
Where does it say that? It only says you can't go larger than the largest value.
The rule states " 1. Split an integer into two smaller integers." If you split 5 into 6 and -1... 6 ain't smaller than 5.
Could a constraint solver just rip through this problem?
Turns out there are 6 unique solutions for [7,5,3] in 6 steps
Earlier quoted context omitted.
None of the implementations support negative numbers, but the rules say integer which includes negative numbers, so that should be a legal move.
Negative numbers would break the game by making the number of possible splits infinite. E.g. 1 could split into [-2, 3], [-3, 4], [-4, 5], etc. It also violates Rule 1 because one of the splits is larger than the original number.
[3, 2]
Creating a zero is useless, you can’t split 3 or 2, and you can’t make a 5.
[2, 1] is similarly stuck.