Tag Info

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
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
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
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 ...

"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
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

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
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
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
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

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
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
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
Accepted

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
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

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
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
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
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
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
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

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
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

...
• 44.1k
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
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
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
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 ...