95
votes
Boolean search explained
The counting principle that applies here is inclusion-exclusion.
$$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$
To make the numbers work out, $\left|X \cap Y \...
- 1,012
63
votes
Accepted
16
votes
Accepted
Why is the counting variant of a hard decision problem not automatically hard?
The reason it's not an automatic theorem that "decision is hard implies that counting is hard" is that these two statements use different definitions of "hard".
A decision problem is hard if it's NP-...
- 81.4k
13
votes
Boolean search explained
Document 1: The cat is on the table
Document 2: My cat is black
Document 3: The dog is under the table
Document 4: What's the name of your cat?
Document 5: This is a black and white photo
Search for ...
- 12.4k
12
votes
Accepted
Count total number of k length paths in a tree
This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th ...
- 1,096
10
votes
Accepted
Count number of non-contiguous occurrences in string
A dynamic programming algorithm in $\mathcal{O}(|S| |T|)$ should do the trick.
Let's denote $S = s_1…s_m$ and $T = t_1…t_n$. For $0\leqslant i \leqslant m$, $0\leqslant j \leqslant n$, let $N(i, j)$ ...
- 12.5k
9
votes
Finding all solutions to an integer linear programming (ILP) problem
"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope.
This problem has a polynomial-time ...
- 21.6k
8
votes
Algorithm to find number of occurrences in mutually exclusive sets
Concatenate all lists, and count which element appears the most times. Using a hash table, this can be implemented in linear time, and otherwise, you can obtain an $O(n\log n)$ algorithm (where $n$ is ...
- 275k
7
votes
Accepted
Seating arrangement problem
Assuming that you are trying to maximize the seating preferences, this problem is NP-Hard =(.
NP-Hardness
Specifically, consider the decision version of this problem: Given a matrix of preferences, ...
- 250
6
votes
Counting islands in Boolean matrices
Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed ...
- 275k
5
votes
Accepted
Counting substrings with a given number of different characters in O(N)
You can solve this in $O(n)$ time using two (well, three) pointers that both move leftward.
Let $S$ be the string. We'll let $i$ range from $n$ down to $1$, and for each value of $i$, we're going to ...
D.W.♦
- 156k
5
votes
Accepted
Sorting an array in linear time
This is a textbook application of radix sort.
Think of the inputs as 2-digit numbers in base $n$. Using a stable version of counting sort, sort the numbers first according to the least significant ...
- 275k
5
votes
Count numbers less than $x$ co-prime to $p$
There's a very fast method if p has few prime factors. Say p is a prime. Then the numbers co-prime with p are all numbers other than p, 2p, 3p, 4p etc. There are x-1 numbers less than x, and of those ...
- 28.3k
5
votes
Accepted
Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems
As I have hinted at in the comments, that your reduction exists is not at all surprising. As in my answer to your previous question, your "Expand and simplify" part takes potentially exponential time ...
- 4,979
5
votes
Accepted
Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$
(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly ...
- 1,110
5
votes
Accepted
Efficient Algorithm to Find the n-th Odious Number
Here is the recursive formula for odious numbers,
$$\begin{align}
a_1&=1,\\
a_{2n} &= 6n-3 -a_n,\\
a_{2n+1} &= a_{n+1} + 2n.
\end{align}$$
The formula can be proved easily by observing, as ...
- 38.6k
5
votes
Efficient Algorithm to Find the n-th Odious Number
Here is an alternative answer, following greybeard's advice. For each $k$, the two integers $2k,2k+1$ contain exactly one odious number. Hence the $i$th odious number is either $2i$ or $2i+1$: it is $...
- 275k
4
votes
Accepted
Finding the number of square prefixes of a string in linear time
Suppose there is an $O(|W|)$ algorithm that computes a slightly different prefix function: $Z[i]$ is the longest prefix of $W$ that is also a prefix of $W[i..n]$. Note then that your answer will ...
- 416
4
votes
Accepted
Counting specific subgraphs
Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory.
The number of connected spanning ...
- 275k
4
votes
Accepted
Counting islands in Boolean matrices
Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual ...
- 12.7k
4
votes
Accepted
Count numbers less than $K$ in array
Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode
...
- 1,331
4
votes
Accepted
Counting on a matrix
Copied from here.
The mathematics
Consider the group $G=S_w\times S_h$, where $S_w$ and $S_h$ are the symmetric group of the sets $W=\{1,2,3,\ldots,w\}$ and $H=\{1,2,3,\ldots,h\}$ with $w$ and $h$ ...
- 101
4
votes
How is the set of functions from ${\{a,b\}}$ to $N$ countable?
You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite.
You only need to find an injection from your set and $\mathbb{N}$, it means that ...
4
votes
Number of substrings possible with even characters
Assuming that your alphabet has constant size, you can solve your problem in linear time in the length of the input string.
Let $\Sigma = \{a_1, a_2, \dots, a_m\}$ be your alphabet and $s = s_1 s_2 \...
- 28.2k
4
votes
Why can’t we use FPRAS for #DNF to estimate #CNF?
The complement of an independent set is a vertex cover, and vice versa.
There is a very simply 2-approximation algorithm for vertex cover.
In contrast, it is NP-hard to approximate independent set ...
- 275k
4
votes
Accepted
What is the (intuitive) relation of NP-hard and #P-complete problems?
The theory of NP-completeness studies decision problems and (indirectly) optimization problems. In contrast, the theory of #P-completeness studies counting problems. In particular, NP is a class of ...
- 275k
4
votes
Accepted
Counting independent sets
No, this problem is well-known to be #P-complete. For more, you can see this question on CSTheory.
- 22.5k
3
votes
Finding the number of square prefixes of a string in linear time
It's also easy to do with a Rabin-Karp-type hash: https://en.wikipedia.org/wiki/Rolling_hash, which you can use to check equality of any two substrings in $O(1)$ time, albeit with a probability of ...
- 416
3
votes
Accepted
Count elements in the real world in constant time by weighing them
Weighing elements works faster than counting them, because the scale is a fully parallel computing device. It sums the weighs of all elements in constant time. Of course you need an infinitely large ...
- 5,931
Only top scored, non community-wiki answers of a minimum length are eligible