Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
std::stack is a standard container like std::vector or std::list. It is a "stack", so a last-in-first-out (LIFO) container.
For offline use if you want to compile it, you need to #include <stack> header (and #include <string> too).
The Kata tests already have these headers included so I gracefully left those includes. (after years thinking about this, maybe it was a little confusing choice...)
This solution seems wrong.
In your isPerfect() you are only checking whether the nodes in the tree equal to 2^n-1 or not.
This will result true in case of non-perfect trees with proper nodecount.
Simple example:
nodeCount = 3; log2(count)+1 == log2(count+1), but it's obviously not perfect.
In C++ after you create an array of arrays you can use
[][]
for multidimensional indexing.But you can not declare an array of array by writing
[][]
!In C++ the mentioned
int ans[4][4]
is just one array:int *ans
. Meaning that it's equivalent withint ans[16]
and the compiler is nice enough to do the reindexing for you.It is used to make sure that every sub-array's dimension is equal, or to ensure that the allocation of the n x n element is contiguous, hence it is one (contiguous) array.
True multidimensional arrays on the other hand can be "anywhere" in memory, only sub-arrays will be contiguous, not the whole.
And to hell: even every sub-array can have different dimension!
The functions are expecting
int **
, so you have to create an array ofint *
first, then the sub-arrays in that.Many solution used the
new[]
allocation... but I really hate the idea to usingnew
withoutdelete
, so I went with static (aka globals :) ).However your solution might be more universal if there would be a need to expand for more operators, in my opinion using structs + map + lambda + stringstream + some jigsaw-puzzle with offsets is a little bit overshoot to the current problem's size.
Although my appreciation for the not copy-paste-from-somewhere solution.
Reading the description again and again... there's already a bold "at most one operation" in it, so not really neccessary to change it.
Although a note might be healpful, like: If you intend to not do any operation on the number, return [n, 0, 0].
Also it might be just my opinion. Seems many had no issue with this. :)
I found an error in the tests:
Input number: 3447799
Expected: equal to [ 3447799, 0, 0 ]
Actual: [ 3447799, 1, 2 ]
Citation from Kata description:
"Choosing the index of a digit in the number, remove this digit at that index and insert it back to another place in the number."
I think from 0 to 0 is not another place.
After completed this Kata, I've looked upon the previous solutions and hell...
The test cases are not adequate! Almost everybody is using recurse and totally forgets about big numbers!
Using recursive algorithm with big numbers may be a suicide way (as may kill your stack).
A recurse modulo-GCD can go into a 127-deep recurse-chain. (which can cost 24000 CPU-tick vs. iterative version's 490 tick worst case)
I highly discourage using that, in particular if there are more ways to avoid the recurse!
Also if you can't be sure that numbers will always be small enough, then you really should: first divide then multiply!
(a * b / gcd() can overflow eg. a = 2^64-2, b > 1)
Note for strings:
repeately building the exact same string from a non-changing "constant" (least common multiplier) in every step in the result-building loop... well you should avoid that too.
(always pre-occupy memory (reserve) if you can estimate the usage)
This code drops out of range exceptions in many many case, eg. if s.size() is 1, 2, 3, 11 etc.
The size of the first 4 substrings is NOT guaranteed to be equal, it depends on input size!
Some would think, this is slow and not efficient... it depends:
int to string (without any optimization) should be a repeated n/10 (div), take reminder (no other assembly operation is required), add a magic number to it.
This is (1 Div + 1 Add) * n, thats (14 * n) tick time. Compiler will inline it and no jumps (16-45 tick) is required.
If you do a modulo and after that a divide... well, you know, modulo is a divide in assembly, so this is already (2 * 13 * n) tick.
Inserting 'if's inside the loop might cause extra jump-calls for 16 ticks.
Note 1: compilers should be able to transform n % 10 into some add+mul+shift in 6-8 ticks, and avoid the div.
Note 2: with extra 4 byte memory you should avoid the modulo and use a multiplication + sub instead!
Note 3: the usual std::count() calls use the same code as manual digit-comparing, there should be no time-difference.
The biggest problem with string is the building-cost: the continous memory allocation and memcopy is what makes the string-version slow.
However you can make it waaaay faster with pre-allocating memory for string with .reserve() (overestimate with the biggest square's size * n), and no more slow allocation!
Drawback: "wasting" memory, eg. if n=5000, overestimate-waste is 4619 byte. I'd live with that.
Another smart idea: not to build a huge string, but after conversion in each step, count immediately as seen in mywtfmp3's solution below, but instead of always initializing a new in the loop, just define and reserve() it outside the loop, and reuse it.
This one is a simple descending iteration with very basic aritmetic (++ and --) and works well with n > 1000 unlike the "best"-around recursive versions (not to mention the ones with hard-wired numbers and upvotes...)
Although I might overcommented this and let the set overwork, oh well. :)