31 votes
Accepted

One element that differs in two arrays. How to find it efficiently?

I see four main ways to solve this problem, with different running times: $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes ...
Mario Cervera's user avatar
29 votes
Accepted

Can the "divide" step in a merge sort be avoided?

The confusion arises from difference between the conceptual description of the algorithm, and its implementation. Logically merge sort is described as splitting up the array into smaller arrays, and ...
psmears's user avatar
  • 477
18 votes
Accepted

What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

It's called "loop fusion". It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in ...
Pseudonym's user avatar
  • 22k
16 votes

One element that differs in two arrays. How to find it efficiently?

The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is: ...
Ilmari Karonen's user avatar
15 votes
Accepted

Maximum subset pairwise not divisible by $K$

Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n_1$ and $n_2$, their sum is divisible to $K$, only if the sum of their ...
orezvani's user avatar
  • 1,944
15 votes

One element that differs in two arrays. How to find it efficiently?

I'd post this as a comment on Tobi's answer, but I don't have the reputation yet. As an alternative to calculating the sum of each list (especially if they are large lists or contain very large ...
reffu's user avatar
  • 411
14 votes

One element that differs in two arrays. How to find it efficiently?

Element = Sum(Array2) - Sum(Array1) I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps. If the number ...
Tobi Alafin's user avatar
  • 1,617
11 votes

Can the "divide" step in a merge sort be avoided?

I guess what you mean is the bottom-up implementation. In the bottom up implementation you start from single cell elements an move upward by merging elements into larger sorted lists/arrays. Just ...
fade2black's user avatar
  • 9,817
10 votes
Accepted

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list: Read the list in chunks of $k$, convert them ...
Yuval Filmus's user avatar
8 votes

Is it feasible to generate every possible RGB image?

The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not ...
D.W.'s user avatar
  • 158k
7 votes
Accepted

Building static hash table with particular collisions

The easiest way is to construct a static hash table $T$ containing all the collisions, in the following form: for each set of keys $S$ which are supposed to map to the same value, single out some $x \...
Yuval Filmus's user avatar
7 votes
Accepted

Is closed form of summation less costly?

I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition. Try being more imaginative. I'm pretty sure that you were taught at ...
David Richerby's user avatar
7 votes
Accepted

Calculating all products of $n-1$ factors when given $n$ factors

Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below. Input: $e_1,\cdots,e_n\in E$, where $n\ge 3$. Output: $p_1, \...
John L.'s user avatar
  • 38.8k
6 votes
Accepted

What problems are believed to have an efficient algorithm?

I'll cover problems that are easy to solve (i.e. in $P$) and problems whose solutions are easy to verify (i.e. in $NP$), and some problems that are probably not, and try to explain why people think ...
Lieuwe Vinkhuijzen's user avatar
6 votes

Problems that feel exponential but are P

For me one of the most efficient algorithms is the Blossom V algorithm that finds maximum weight perfect matching in a general graph: https://en.m.wikipedia.org/wiki/Blossom_algorithm
Dmitry Kamenetsky's user avatar
5 votes
Accepted

Efficient algorithm for finding weakly connected components

Replace every directed edge $u \to v$ with an undirected edge $(u,v)$. Now use any standard algorithm for finding connected components in the resulting undirected graph. One standard approach for ...
D.W.'s user avatar
  • 158k
5 votes
Accepted

Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate: Stage 1: Calculate $M^...
gnasher729's user avatar
  • 29.4k
5 votes
Accepted

Parsing CFLs (simulating PDA vs CYK algorithm)

Wikipedia mentions that the class of deterministic context-free languages can be parsed in linear time, using an LR parser. In contrast, the fastest algorithm for parsing general context-free ...
Yuval Filmus's user avatar
5 votes
Accepted

Data structure for A*'s "open" set

I think I never heard the term "Open Set" as we usually call it "OPEN list" (and by convention we use upper-case letters). I mention this to highlight the fact that this structure is closer to a list ...
Carlos Linares López's user avatar
5 votes

Problems that feel exponential but are P

For me all classic and the more recent more efficient algorithms to verify or find a minimum spanning tree (MST) of a connected edge-weighted graph are good candidates. Many of these algorithms are ...
John L.'s user avatar
  • 38.8k
5 votes

Data structure for finding max, inserting and deleting in O(1) and O(n) space

Suppose we have such data structure. We can find in $O(1)$ the max, delete the max in $O(1)$ and repeat it $n$ times. Hence, we can sort $n$ numbers in $O(n)$. Therefore, constructing such data ...
OmG's user avatar
  • 3,572
4 votes
Accepted

Efficient algorithm to compute the minimum of multiple piecewise linear functions

This is basically an instance of the line segment intersection problem. One standard approach is to use a sweep line algorithm. For instance, the Bentley-Ottman algorithm would be a reasonable ...
D.W.'s user avatar
  • 158k
4 votes

improving java 8's implement to hash map using avl tree

This page on Oracle's website says: The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins ...
tsleyson's user avatar
  • 3,128
4 votes
Accepted

What is the fastest way to check if an integer is divisible by another?

Integer division The best algorithm known for integer division has running time that is slightly more than linear, i.e., a bit more than $O(n)$. In particular, it is something like $O(n \lg n 2^{\...
D.W.'s user avatar
  • 158k
4 votes

Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?

The way i see it, talking about slowdowns on simulations of a specific Turing machine $M_0$ doesn't make much sense. I could always just run $M_0$ and call this a simulation, which will result in no ...
Ariel's user avatar
  • 13.4k
4 votes

Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

There's two levels you can analyze parallel speedups with matrix exponentiation: The "macro-algorithmic" level that decides which matrices to multiply, and the "micro-algorithmic" level where you can ...
Kurt Mueller's user avatar
4 votes

Why is it most efficient to resize a dynamic array to 2 * array.length()?

Consider a model in which elements are only added, one at a time, and once an array is full, it is increased in size by a factor of $C$. Suppose also that resizing an array of size $x$ costs $Cx$. ...
Yuval Filmus's user avatar
4 votes
Accepted

Is it possible to implement a WeakMap with primitive keys and weak values?

Okay. My confusion with this question is that I assumed that what you wanted is a weak value map, which it appears is what you want, and this can be implemented in a straightforward manner (at least ...
Derek Elkins left SE's user avatar
4 votes

Efficient point grouping algorithm

My Solutions I will try to elaborate on what solutions I found, their implementations and those implementation's running time. As I don't have any real computer science background, please point out ...
Banana's user avatar
  • 235
4 votes
Accepted

Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

It's unlikely that a data structure exists that supports both $insert(\cdot)$ and $find(\cdot)$ queries in $o(n/\log^2 n)$ time, since if it did, then we could use it to solve the 3SUM problem in $o(n^...
j_random_hacker's user avatar

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