21
votes
The fastest way to find one unique value when all other values are the same
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 ...
- 2,983
20
votes
Accepted
Calculate square of a number without multiplication
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 &\...
- 97k
18
votes
Accepted
Check if one string is a permutation of another using Python
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 ...
- 143k
18
votes
Accepted
Finding the most popular element with C# given O(1) space complexity requirement
You don't have \$O(1)\$ space complexity at the moment, OrderBy and OrderByDescending (used wrong as pointed out in the other ...
- 20k
16
votes
"Algorithmic Crush" problem hitting timeout errors
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.
...
- 6,118
14
votes
Accepted
Find the total number of ways W, in which a sum S can be reached in N throws of a dice
1. Review
The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but:
...
- 49.4k
13
votes
The fastest way to find one unique value when all other values are the same
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 ...
- 2,301
12
votes
Accepted
Finding Pythagorean triplet in array
A couple of notes on your code before going into alternative solutions.
In your findTriplet method, you are doing:
...
- 9,203
11
votes
Accepted
Finding whether there exists a pair of numbers in a set having a given product
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 ...
- 49.4k
11
votes
Accepted
Does my Linklist implementation have memory leaks?
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, ...
- 64.9k
11
votes
Binary Search written in python with O(n)
It's not really a binary search if it is not O(log(n)).
Binary search only works on sorted inputs and it takes advantage of the fact that it is sorted to achieve ...
- 5,015
10
votes
Accepted
Sum the exponents of the prime factors of a number
In addition to the other answer:
There is no need to generate all primes up to n. You can generate them up to sqrt(n). If ...
- 5,580
10
votes
Accepted
Solving 'decent numbers' that follow specific division rules
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\$, ...
- 6,562
10
votes
Accepted
Google's Python exercise about lists very different from the given solution
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 ...
- 535
10
votes
Accepted
Finding number of number pairs with given difference
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 ...
- 58.6k
10
votes
Finding a max element in an array in Java
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 ...
- 143k
10
votes
Accepted
Find the number of K-Complementary pairs in an array
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, ...
- 9,203
10
votes
Accepted
Sort an array of 0s, 1s and 2s in Java
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....
- 21.4k
10
votes
Accepted
Regular Expression Evaluator
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 ...
- 9,249
10
votes
Accepted
Time and Space Complexity of Prime factorization
isPrime()
Complexity
This function contains a simple loop that iterates up to Math.sqrt(number) times, so assuming ...
- 32.9k
9
votes
Accepted
Codility MaxCounters peformance in Python capping out at 77% performance
What hurts your performance is filling the array with max_count. So don't do it. Imply it. The trick is all there, and it makes this slightly different from trying ...
- 2,671
9
votes
Find maximum difference between values in an array
What does this algorithm do? It finds the smallest and greatest number in an array and creates the difference of them.
Nope.
Consider {5, 2, 1}. The pseudo code returns 5 - 1 = 4 which happens to be ...
- 1,010
9
votes
Accepted
URLify a string using Python
Your complexity analyses look correct to me. I would just say, in short, that this function works in O(n2) time.
Note that this is an awkward exercise to do in Python, or any language in which ...
- 143k
9
votes
9
votes
Accepted
Find the smallest positive integer that is absent from a given array
I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; ...
- 2,889
8
votes
Accepted
Finding overlapping time intervals
You could make the Meeting class generic with the T : IComparable<T> constraint. Thus you'll be able to use any type as a ...
- 4,579
8
votes
Accepted
Sufficient implementation of subset sum for 45 min interview
Bug
I ran your program, replacing 100 with 6. This should have found the subset {2,4} as a ...
- 28.5k
8
votes
Accepted
Finding the most common character in a string with a hash map
Normally operations on a hashmap should be pretty much constant (O(n)=1), so it's something like O(n) = n + 2*m (number of characters in the String plus twice the amount of different characters in the ...
- 581
8
votes
Accepted
Function to check truth value of a specific statement
Make the function return True or False.
You can use all and a generator comprehension ...
- 41.8k
Only top scored, non community-wiki answers of a minimum length are eligible