# Tag Info

17

A few things: Naming: It's neither Fibonaci, nor febonani, nor fibonanci it's fibonacci. Please get your names to reflect what you're actually talking about and not some disfigured mutation of it :( memoized OTOH is a relatively nice name, I'd probably prefer memoizedFibonacciNumbers, but that's a thing of preference Calculating: quoting wikipedia: ...

14

No, not $O(n)$. Not even close. I'll get back to this later though. First, the code: It's a little difficult to tell what your loop logic is. curr is getting incremented each time, but i isn't... whereas typically we'd use i as a loop index. I'd propose using i as the loop index, and then keeping a humble number count named count (or num_humbles or ...

13

There are some other Java gurus around here who might know some Java-specific tips and tricks, but... I want to look at something else you're doing in the algorithm. First of all, we know from the problem statement that any positive integer will have at least 1 possible answer, that is, itself. What we can also know from basic math knowledge is that the ...

13

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}} + \frac{1}{2} \right\rfloor$$ So the 484th Fibonacci number would be equal to: \left\lfloor \frac{\varphi^{484}}{\sqrt{5}} + \frac{1}{2} \right\rfloor \approx 6....

12

There are some major issues with your approach, the major one being that it is going to terribly break down for really large numbers. But if you want to go with it, here are a couple of improvements: Don't use a dictionary. If your indices are consecutive integers, then a list is the right data structure. You already know that most of your entries are going ...

12

Assuming you're using the current c++ standard, since you don't specify in your question. Prefer stoi to atoi. atoi has issues. Prefer standard int types: std::uint128_t instead of unsigned long long int Create a type alias for your map type since you use it a lot. Don't include unnecessary headers in the fibbonacci.h file. Include them in the ...

12

Is this a generator or a calculator? Generators are objects that behave like iterators, yielding the next value on every call. std::map<int, unsigned long long int> __fib_result_map = initializeMap(); #ifndef __fibonacci #define __fibonacci Know the rules regarding underscore usage. From the C++ Standard: 17.6.4.3.2 Global names [global.names] ...

11

Concept You have called this a "Longest Increasing Subsequence" problem, but it's not, is it? It's counting all possible sequences of a specific length, not just the longest. As a result, I think you may have confused yourself in a few ways.... Naming Your variable and method names are ... horrible. Variables should always be useful names, and, while N ...

11

1. Review The function coinChange carries out three tasks: (i) read the input; (ii) solve the problem; (iii) print the solution. This makes it hard to test, because it's hard to run the code on different problem instances (you have to feed it the problem in text form on standard input), and becaue it's hard to automatically check the output (you have to ...

10

If someone were to say: isPowerOf2(9223372036854775808) what would your function do? For a start, it will end up with an array of a very, very large size.... that can't be right.... ... next, computers are binary machines, and binary numbers are powers of 2.... there has to be a way for the base infrastructure to make that easier? Well, there is. When ...

10

Recursive Solution Code-wise, I see no issues. The one thing I'd point out is that it might be clearer to name your functions A and B instead of Nth and Aux, since the problem has to do with finding A and it isn't readily apparent what Aux means. It's a little unclear, but not a dealbreaker. Bottom-up method I don't really understand why your memoized ...

10

#include <cstdio> If your goal is to write C++, you're really off to a bad start using the C standard I/O library. const unsigned short n = 20; The modern way to do compile time constants is with constexpr. But I don't understand why you chose to use unsigned short for all your indexing calculations. Any operations you try to do on it will ...

9

You should have a look at Python's official style-guide, PEP8. One of its recommendations is to use PascalCase for class names and lower_case for function and variable names. Since you read all words into memory anyway, you can just write: with open(in_file_name) as fp: self.words = fp.read().split() This is because split splits by default on all ...

8

@Vogel612 has already mentioned all major defects and areas of improvement in your code. I want to talk about one more thing: Your package naming is horrible. You are using com.java.fib, please do not ever do that again, because: Although Java classes are prefixed with java.*, it still creates confusion as people might think this is a library class. In ...

8

Currently, your code is next to unreadable. The variable names are too cryptic. Names like den and S don't tell anything about the context of the variable. Please, use descriptive names. You don't give space for your variables to breath. You crammed everything up and that makes it harder to read. An example: for(i=0;i<n;i++) temp[i] = S / den[i] ; ...

8

Bug You code is currently too simplistic. All it does is make change from the highest denomination possible. It fails on the following input: Enter the total change you want: 6 Enter the no. of different denominations of coins available: 3 Enter the different denominations in ascending order: 1 3 4 min no of coins = 3 Your program thought the change ...

8

The loop # Move every element in the previous generation up one index into the new generation for k in range(0, len(previous)): answer[k + 1] = previous[k] makes the next allGenerations list one element longer than the previous one. After n iterations you have lists of lengths 1, 2, ... n, making them $O(n^2)$ total. Just populating ...

8

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 p will consume almost all of the memory used by this routine, it would be more productive checking whether you need the whole grid or can get away with just a few rows at once. Consider using ...

8

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 should check whether the number is A perfect square (the answer is obviously 1), or is a sum of 2 squares (the answer is obviously 2), or not a Legendre's number,...

8

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 longest_common_substring. Tricky Code Your dp matrix is properly allocated to the size m+1 by n+1. When you index your matrix, you access [i-1][j-1] with $0 \le i \lt m$ and $0 \le j \lt n$. This ...

8

Your code performs one recursion per character and recursion depth is limited. For long inputs, your code will raise RecursionError: maximum recursion depth exceeded. Replacing recursion with an explicit loop solves the issue. Also, if you start the calculation at k = 1 with memo[-1] and memo[0] properly initialized and then work upwards to k = len(s), the ...

7

I do have a lot of comments, but I find your solution pretty good. The algorithm makes sense, and your comments make it easy to follow. The function is closer to a computation than a search, so I wouldn't call it find…. The N parameter is redundant, since it can be deduced from the dimensions of prices. On the other hand, color_names is hard-coded (and ...

7

using namespace std using namespace std; Count the number of characters you use with this (twenty) and compare to the number of characters you save by having it (five). Wouldn't it be better to just say std::map instead? Even in fib_cpp.cpp, you only save fifteen characters for a net increase of five. std::vector vs. std::map map<int, ...

7

For each i = 0...number, your method stores a std::list containing the complete sequence of intermediate numbers from 1 to i. Each list is created by copying the list from the optimal predecessor and appending i. Even for a single i, path[i] may be assigned a new list up to three times. That is a lot of copying which consumes a lot of time. It can be ...

7

Integer Division In Python, 10 / 2 is equal to 5.0, not 5. Python has the integer division operator (//) which produces an integral value after division, instead of a floating point value. To prevent storing both int and float keys in the count dictionary, you should use: count[n] = collatz_count(n // 2) + 1 Cache Your count cache works nicely. ...

6

What quickly jumps out: typedef vector<dimension*> VecDim; // ^ Pointer typedef vector<dimension*>::iterator VecDimIter; // ^ Pointer Its very rare to see "raw" pointers in good C++ code. This is because now you have to do memory management on the code. Pointers are useful for implementing the ...

6

Missing methods The posted code is missing the schedule_left() and CreateOutputFile() method. Style you should always be consistent in the style you use. Switching from not using braces {} to using them for single for loops should be avoided. The same is true for single if statements. dead code should be deleted if you decide to not using braces ...

6

Everything is in main. It's called main. It's not called everything. You have written no functions here, but you should. Writing functions is a way of giving names to chunks of code that are independent, testable, and give a desired result for a given input (and do that in the same way every time). Plus, it goes a long way to making our code far more ...

6

This Code Review, so let us review your code, before proceeding to questions and optimisations. Code and style review Choose better names – According to python style guide, PEP8, you should use snake_case for variables and functions. In addition what does dp, acc stand for? And in general one should avoid single letter variables except in tight loops ...

6

If I were Alice, the most optimum strategy, well, there are two. The binary search, or in Python is the bisection method, or I would use the Fibonacci method, which is mathematically superior and faster than the binary search method. Anyway, that would be what Alice would have to do to get to the number in the least number of guesses. Bob, on the other ...

Only top voted, non community-wiki answers of a minimum length are eligible