57
While other answers make good points, I have to wonder why you are using recursion. This is such a simple problem to solve with a for loop.
I assume that you are not supposed to start from any index other than index 0, so consider the following routine:
public int searchArray(int[] arr, int elem) {
for (int i = 0; i < arr.length; ) {
if (...
32
The problem is in \$O(n)\$. Consider the case that 200_success describes.
You have a sequence of alternating 1 and 2's where a single 1 is replaced by a 3.
When you are asked to search for a 3 you know, after inspecting the first element, that it will have an even index. But if every odd index holds a 2 then any even index can hold a 3, so you can ...
26
Rewafadhabihlgdity
(If you can't tell, that is supposed to say 'readability'). Leaves some things to be desired.
Variable names: All your variable names are three characters or less. This makes it very hard to read your code. Renaming r to playerCount is a start, and S can be called strengths. so1 and so2 should also be renamed, along with t, p and q. Make ...
19
A more efficient way to do this is to keep doubling the product while you can....
So, for example, \$5^2\$ is:
$$\begin{eqnarray*}
5 +& 5 &\longrightarrow 10 \\
10 +& 10 &\longrightarrow 20
\end{eqnarray*} $$
then add the last 5 to get 25.
This can be done efficiently by using bit shifting:
public static int sqr (int val)
{
int ...
19
Yes, len(str) should be O(1) in Python. (Good question!) Each of your for loops is O(n), so your whole function is O(n).
Your counting loops could be written more compactly as
for char in first_string:
count_first[char] = 1 + count_first.get(char, 0)
The epilogue could be simplified to
return count_first == count_other
It pays to get familiar with ...
18
You don't have \$O(1)\$ space complexity at the moment, OrderBy and OrderByDescending (used wrong as pointed out in the other answer(s)) will have a non-constant space complexity.
Since runtime is not the problem here, we can make this a space complexity of \$O(1)\$ pretty easily:
Tuple<int, int> GetItemWithMaxCount(int[] items)
{
var maxCount = ...
17
This is beautiful, easy to read, and well-documented code. It is a joy reading this code, and there is very little to improve on the Java side.
The greatest weakness that shows in this code is not your skill with Java (which surpasses mine by far), but your knowledge of the English language.
In the addEdge JavaDoc you talk about arcs not edges.
The ...
16
Constraints
\$3 ≤ N ≤ 10^7\$
\$1 ≤ M ≤ 2 \cdot 10^5\$
\$1 ≤ a ≤ b ≤ N\$
\$0 ≤ k ≤ 10^9\$
You should verify that every value you read from the user is a valid value in your program.
As far as complexity goes, a suffix tree with a complexity of \$O(N\log{}N)\$ compared to your current \$O(MN)\$ solution that adds difference to every value in ...
14
You never need to look backwards if you start at 0.
Proof by induction over algorithm steps j:
For j = 0, i(j) = 0, you cannot go backwards.
For j > 1, there are two cases: First one, we found our number. Second one, there is a difference diff(j) = abs(elem - array[i(j)]). Then no number in array[i(j),i(j)+diff) can contain elem. By induction hypothesis, ...
14
1. Review
The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but:
>>> get_sum_dp(0, 0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "cr161002.py", line 32, in get_sum_dp
t[1][j] = 1
IndexError: list index out of range
The name get_sum_dp could be clearer (what does "dp" mean? ...
13
Let's see this mathematically. I am assuming that a is an ascendingly sorted array. I start with indexes from 1, to get better readability (by avoiding n-1 as often as possible).
We want the following sum:
$$\begin{array}{l@{}l@{}l@{}l}
\sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_j - a_i) = (a_2 - a_1) &+ (a_3 - a_1) &+ (a_4 - a_1) + & \dots + (a_n - ...
12
Here's some generic advice first:
Avoid single-letter parameter names. For small loops i is fine, but it shouldn't leak into method signatures--especially when index is only four more letters.
Be consistent with if-else. You have two if blocks that both return from the method, either use else with both or neither. Otherwise it appears at a quick glance that ...
12
A couple of notes on your code before going into alternative solutions.
In your findTriplet method, you are doing:
if (squareA == sum) {
return true;
}
return false;
which is more concisely expressed as
return squareA == sum;
Your main getTriplets method checks whether (i != k) || (j != k), but this isn't possible by construction: k starts at i+j ...
11
I plan to think up a better algorithm later and post an answer on that, but for now, I'd like to offer a critique of your existing code.
Typically using namespace std; should be avoided in favor of either using the std:: qualifier or just importing the identifiers you plan to use at a function level. (E.g. inside of main, doing something like using std::...
11
Why don't you simply use an array of strings, as in:
String carCodeSet[] = {"FAQ025","QEF025","QEF037AB", /*...*/ };
this seems to me cleaner. Of course the HashSet would have better performance if the list of codes is very long... but maybe for 20 items a linear search on the array is not bad.
The String.contains method poses some problems in the fact ...
11
Use Collection.contains.
That reduces your if statement to the following:
if ( filterCarCodes.contains(auto.getCarCode()) ){
//stuff
}
You can initialize the Collection once with Arrays.asList, using a String array. Then declare it as a static final class variable and you're pretty much set. An alternative is the HashSet you described - via Arrays....
11
The algorithm description is good, but the implementation of find is \$ O(n) \$, so the overall runtime is actually \$ O(n^2) \$.
Detailed review follows:
There are no docstrings. What does each function do? How do I call it? What does it return? Are there any constraints on the parameters, for example do the inputs have to be sorted? or do they have to be ...
11
It does not appear to be leaking memory (except on exit). However, there are a number of things you can do to improve this code.
Fix the formatting
Code that has poor formatting is hard to read, understand, and maintain. For that reason, you should strive to have nicely formatted code. In this case, that means fixing indentation and inserting whitespace. ...
10
Unfortunately, both solutions are wrong as they don't pass the following JUnit tests:
@Test
public void testSolution() {
FishSurvivor fs = new FishSurvivor();
int[] a = { 4, 3, 2, 1, 5 };
int[] b = { 0, 1, 0, 0, 0 };
assertEquals(2, fs.solution(a, b));
a = new int[] { 4, 3, 2, 1, 5 };
b = new int[] { 0, 1, 0, 1, 0 };
...
10
You have taken a very literal, brute-force approach to solving the problem. As @ChrisWue points out, trying to compute 500! will kill you many times over. Instead of multiplying the numbers out, try factoring instead. Here is an outline of a solution that might work:
For every \$n = 2, 3, \ldots, N\$, find the prime factorization of \$n!\$. This is not ...
10
At the heart of your problem you are trying to solve a single linear Diophantine equation. Because 3 and 5 are coprime, their greatest common divisor is 1, and hence your equation, \$3a + 5b = n\$, will always have an integer solution. It is easy to check that \$a = 7n\$, \$b = -4n\$ is indeed one such solution. Of course you want both \$a\$ and \$b\$ to be ...
10
Current complexity is \$O(n^2)\$, you can accomplish this with \$O(n \space log \space n)\$ instead by sorting the array first and then loop through the elements.
Let's say that you know that the array is sorted, and the array is for example 4 8 15 16 23 42 and you want to find the diff 7:
Let's initialize two variables, lowIndex, highIndex to both 0.
Now ...
10
Yes, this is O(n), because you visit every element once. You can't possibly do better than O(n), because there is no way to be sure that you have found the maximum value without inspecting every element. (There are two exceptions. If the array is known to be sorted in some way, then you can skip straight to the maximum. Also, if you ever encounter ...
10
Current algorithm
The time complexity of the current solution is O(N²): for a given array of length N, it needs to loop through its elements from 0 to its length, and then for each of those, loop again through the elements after it. Note that it is still O(N²), even with the logic of avoiding duplicate indexes (if the pair (0,1) was a solution, it always ...
10
Descriptive names
private static void printSortedArr (int[] arr) {
I don't like these names. I would rather write out array if that's what's being said. E.g.
private static void printSortedArray(int[] numbers) {
Now I don't have to figure out that Arr is short for array. And numbers is more descriptive than array anyway.
Favor arrays over ...
10
Bug
There is a case that requires NFA instead of simple DFA to recognize string (of course it is possible to convert NFA to DFA):
eval("aaab", "a*ab");
Gives false, even though the string matches the regex. Disallowing same character after * fixes the problem too.
Style
why-is-using-namespace-std-considered-bad-practice.
Pass by const reference for ...
9
This can be done in O(1) time, if it is ok to use O(n) time to build a lookup-table just once. If the array stays the same, and you're going to search multiple times, this might be a good approach. The following pseudocode assumes you're going to search the whole array (from index 0), and returns the first index where the element is found. It can easily be ...
9
import java.util.Stack;
class Solution {
/* A POD struct to aggregate fish that will be eaten or not eaten together */
/* If the front fish is larger than any fish in the school (ie they are ordered) */
/* and the front fish is eaten, the rest of the school will also definitely be */
/* eaten. Any fish that the front fish can eat will not be ...
9
This is a specialised instance of the Subset sum problem, which is NP-Complete in the general case.
Of course, when working with a small subset size that is known in advance, we can significantly cut down on the running time (at worst checking C{n, k} values, where n is the number of values in the search space and k is the size of the subset we're looking ...
9
Although this is not related to optimization, it looks like you could improve some of the ways you use loops. If you're using a counter, chances are you should use a for loop:
for (int i = number; i > 0; i--) { /*...*/ }
This works best if the loop counter initialization is pretty short. But if it's too long and should remain on its own line, then ...
Only top voted, non community-wiki answers of a minimum length are eligible
