13
votes
Performance of dynamic Fibonacci generator and dead rabbits
With regard to your time complexity:
With your calculation of the nth Fibonacci number, you could do it in \$O(1)\$ time by using the relation:
$$F_n = \left\lfloor \frac{\varphi^n}{\sqrt{5}} + \...
- 3,800
10
votes
Project Euler #15: counting paths through a 20 × 20 grid
#include <cstdio>
If your goal is to write C++, you're really off to a bad start using the C standard I/O library.
...
- 16.5k
8
votes
8
votes
Accepted
Project Euler #15: counting paths through a 20 × 20 grid
Why are you using unsigned short?
I presume the answer is somewhere along the lines of worrying about memory usage. There isn't a problem with that, but given that ...
- 6,106
8
votes
Accepted
Find smallest number of squares that sum to a number
Not an review, but an extended comment:
I don't know how this solution can be optimized. The expected solution is radically different, and is based on a couple of theorems from number theory.
You ...
- 58.7k
8
votes
find longest common substring in space O(n)
PEP 8
You are following most of the PEP 8 style guidelines. One that you are breaking is method names should be snake_case; your function should be named ...
- 35.3k
8
votes
Accepted
Printing the number of ways a message can be decoded
Your code performs one recursion per character and recursion depth is limited. For long inputs, your code will raise RecursionError: maximum recursion depth exceeded...
- 3,110
8
votes
Recursive solution of ordered Coin Combinations II (CSES)
Normally I do a design review first, then review the code itself. This time I’m going to switch it around.
Code review
Before I get into review this code, I just have to say that the sample solution ...
- 16.5k
8
votes
Find maximum value of recursively-defined "fusc" function
Don't mix C and C++ code
Your code is a mix of C and C++. While you can use functions from C's standard library in C++ code, I recommend you avoid it and write as much as possible using just functions ...
- 69.3k
8
votes
Accepted
C++ - Secretary Problem using dynamic programming
Overview
About your use of C-arrays: you need to justify this. Sure using them to learn is fine, but here you are not really using them in that way.
In C++ we tend ...
- 97.7k
7
votes
Accepted
Project Euler #14: Longest Collatz Sequence starting point
Integer Division
In Python, 10 / 2 is equal to 5.0, not 5. Python has the integer division ...
- 35.3k
7
votes
Sum of bitwise XOR of each subarray weighted by length
Choosing int as the return type for main() for portability and compatibility":
Portably, ...
- 10.1k
7
votes
Sum of bitwise XOR of each subarray weighted by length
long long int main() invokes UB. main must be declared as int.
...
- 58.7k
6
votes
Accepted
Dynamic programming solution to "Climbing Stairs"
The code in the post has to compute the \$i\$th Fibonacci number, \$F_i\$, for every \$i \le n\$, in order to compute \$F_n\$. It's possible to do much better than that, by using the recurrence $$ \...
- 50.1k
6
votes
Find smallest number of squares that sum to a number
Review of your existing code
(with some small performance improvements):
nums = {}
for x in range(1,n+1):
nums[x] = 1
creates a dictionary with keys from <...
- 24.2k
6
votes
Accepted
(Codewars Kata) Memoised Log Cutting
I see three problems with this function:
Why calculate the values up to len(p), when you are actually interested in p[n] (which ...
- 41.7k
6
votes
Minimum path sum in a triangle (Project Euler 18 and 67) with Python
General
Since the problem gives the triangle as a text file, your program should probably be able to read that file. It would be quite a lot of work to input them manually, and when using the file ...
- 41.7k
6
votes
Accepted
Maximum sum combination
Often it is the case that reformatting the data leads to insights. Let's take a look at the test case:
A: 1 2 3 4 5
B: 5 4 3 2 1
Now let's suppose that we ...
- 15k
6
votes
C++ - Secretary Problem using dynamic programming
Minus the call to std::cout, you have a program that is all C. So why not use C and a C compiler instead of running almost C code under a C++ compiler?
Martin ...
- 10.1k
6
votes
LeetCode 678: Valid Parenthesis String, Recursion memoization to DP
When you use dynamic programming / memoization, document the meaning of the table entries or the function parameters/result. I usually write that down before I start coding. Here for example:
...
- 1,080
5
votes
Accepted
Maximum sum of non-consecutive elements of an array
The algorithm is conceptually fine: it's simple and it works.
I don't like the use of iter() and next(), though. When you ...
- 146k
5
votes
Accepted
Counting subsets with sum not exceeding some limit
The problem is actually with your algorithm, not with your C++ code. The time complexity of your solution is \$O(2^n \times \text{polynomial}(n))\$, which is too much for the given constraints.
You ...
- 5,660
5
votes
Splitting a rectangular chocolate bar
Readability and understandability of the code is (usually) much more important that some 'clever' algorithm. This is because almost all code needs to be debugged, modified, updated, understood by ...
- 2,928
5
votes
Accepted
"What is the fastest solution for finding the maximum sum of a subarray?"
Can't get much better
First of all, I would have to agree with the commenters that your solution is fine. Any further gains upon your solution would probably depend on random factors in the Leetcode ...
- 28.9k
5
votes
Project Euler #15: counting paths through a 20 × 20 grid
Package your code into meaningful operations as carefully named functions.
There will be a day that you or someone else is going to maintain some code, they'll open the file, and they'll see ...
- 6,770
5
votes
Accepted
The Dungeon game
Potential Drawbacks of Results
As highlighted by @Mitchel Paulin LeetCode's performance test aren't reliable. I wrote my own answer and got a range of timings from 44ms in >96.53% bracket, but the ...
- 44.6k
5
votes
Accepted
Length of the longest common sub sequence bottom up
x and y are terrible variable names. length1 and length2...
- 35.3k
5
votes
Accepted
LeetCode: Burst Balloons C#
Some things come to mind when I read your code.
There is a nice feature on arrays in C# called CopyTo(). It gives you the possibility to copy an array without ...
- 236
5
votes
Accepted
Minimum path sum in a triangle (Project Euler 18 and 67) with Python
Minor Cleanup
Contrary to @Graipher's opinion, I find your max_triangle_sum implementation is reasonably clear. Although, I'm not sure I'd refer to it as dynamic ...
- 35.3k
5
votes
Accepted
LeetCode on Longest Palindromic Substring in Python
Disclaimer: Not a Code Reviewer
Here are some short comments though:
You're looping though twice.
That'd make it brute force.
Brute force does usually fail for some medium and hard questions on ...
- 3,732
Only top scored, non community-wiki answers of a minimum length are eligible