59
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 (...
34
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 ...
21
Benchmarks!
Benchmarks for lists with a thousand or a million elements, with the unique element in the middle of the array to reflect the "typical"/"average" case. The results are times, so lower=faster.
n=1000
0.90 find_uniq_Jacques
1.18 find_uniq_tinstaafl_1
0.59 find_uniq_tinstaafl_2
0.88 find_uniq_GZ0_1
0.14 find_uniq_GZ0_2
0.88 ...
20
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 ...
18
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 ...
15
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
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 ...
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 - ...
13
No matter how the array is traversed, the distinguished element can occur at the end of the traversal. Therefore, it is necessary to go through the entire array in the worst case and there does not exist an algorithm that can have a better worst-case time complexity than \$n\$. However, in practise, the actual runtime of your implementation can be improved, ...
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 ...
12
One of things about the solutions presented so far, is they all require iterating over all the elements at least once.
Using an iterative approach allows you to short circuit the loop when the unique item is found. something like this would work:
def find_uniq(arr):
for i in range(len(arr)-1):
if arr[i] != arr[i+1]:
if i == 0 and arr[...
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
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 ...
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
This code involves sorting an array of \$N\$ elements, so it has \$O(N * log N)\$ time complexity. To achieve \$O(N)\$ time complexity, you need to avoid sorting input data. Instead, you can create an array of \$N\$ bools to check that each number from \$1\$ to \$N\$ is present in the input array.
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
In a nutshell, yours is better, for two reasons.
First, Python isn't designed for speed. It's decently fast, but the goal is code like yours: so clear, concise, obvious, and readable that anyone can glance at it and immediately see what it does. You can then spend the rest of the project's development time working on the difficult problems (like attending ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
