Ad
  • Default User Avatar

    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...)

  • Default User Avatar

    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:


    O
    /
    O
    /
    O

    nodeCount = 3; log2(count)+1 == log2(count+1), but it's obviously not perfect.
  • Default User Avatar

    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 with int 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 of int * first, then the sub-arrays in that.
    Many solution used the new[] allocation... but I really hate the idea to using new without delete, so I went with static (aka globals :) ).

  • Default User Avatar

    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.

  • Default User Avatar

    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. :)

  • Default User Avatar

    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.

  • Default User Avatar

    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)

  • Default User Avatar

    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!

  • Default User Avatar

    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.

  • Default User Avatar

    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. :)