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 \...
200_success's user avatar
  • 1,012
63 votes
Accepted

Boolean search explained

Hint: The search x AND y will result in 10 000 hits.
Yuval Filmus's user avatar
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-...
David Richerby's user avatar
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 ...
Vor's user avatar
  • 12.5k
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 ...
Antti Röyskö's user avatar
11 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)$ ...
Nathaniel's user avatar
  • 15.6k
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 ...
Pseudonym's user avatar
  • 22.1k
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 ...
Yuval Filmus's user avatar
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, ...
Phylliida's user avatar
  • 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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 159k
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 ...
Yuval Filmus's user avatar
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 ...
gnasher729's user avatar
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 ...
dkaeae's user avatar
  • 5,017
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 ...
integrator's user avatar
  • 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 ...
John L.'s user avatar
  • 39k
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 $...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Mihai's user avatar
  • 416
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 ...
orlp's user avatar
  • 13.4k
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 ...
Teodor Dyakov's user avatar
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$ ...
NotDijkstra's user avatar
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 ...
Saad Balbiyad's user avatar
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 \...
Steven's user avatar
  • 29.5k
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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.
Juho's user avatar
  • 22.6k
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 ...
Mihai's user avatar
  • 416
3 votes

How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\{0,\ldots,m\}$, and let $C(n,m) = |\mathcal C(n,m)|...
Yuval Filmus's user avatar

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