# Questions tagged [counting]

The term Counting in Computer Science is usually used to refer counting objects in certain arrangements or with certain properties.

145 questions
Filter by
Sorted by
Tagged with
91 views

### How hard is APPROXIMATE-#SAT? [closed]

It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete. It is also suspected (somewhat less widely) that even deciding SAT should ...
414 views

### Find smallest enclosing circle

On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known ...
31 views

481 views

### How many 3-SAT expressions with up to N variables are satisfiable?

TL;DR There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-...
136 views

### Count numbers less than $K$ in array

Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A_i<K$. What is the easiest way to pre-process the array and ...
71 views

### Proving or disproving a set of total functions is countable

Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. ...
796 views

### Radix, merge, counting sort and when to use

Okay can't figure this out. I want to make sure I understand it. There are n random keys each being float numbers with p decimal places. So, for example, 123.456, 343.645, 234.543, 863.238, 956....
60 views

### Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays

$k = \Theta(n)$ The arrays consist only natural numbers $1$ to $n$ The sum of the length of all arrays = $\Theta(n)$ It should return the $k$ original arrays, each sorted on its own. The running ...
43 views

### Approximate count per element in list/stream via Counting Bloom+Morris

I've a large list A of elements. Given another list B of elements, I need B to be sorted by ...
259 views

### Sorting an array in linear time

I need to find a method to sort an array in $O(n)$ time complexity. I saw this link, however I'm not sure how to apply it to the elements I need. Input: an array $A$ of length $n$, containing ...
64 views

### On lowness of $\oplus P$

$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$). Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$? Are there complexity classes $\mathcal C$ ...
1k views

### How to count all contiguous subsequences with positive sum?

I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$. I need to count how many contiguous subsequences have positive sum. This pseudocode demonstrates ...
140 views

### Count Wildcard Parenthesizations of a String

Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is ...
297 views

### Using Pascal's Triangle to implement queues and stacks using heaps

I have the following question as homework in an algorithms, analysis and data structures class: And here's an answer I wrote up: A queue is a first-in-first-out data structure. A heap is a data ...
101 views

### Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT

A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that: There exist a clause where all variables are unsatisfied. Unfixing any variable make every clause contain at least ...
357 views

### How to use Bitmasking to solve this problem?

http://codeforces.com/problemset/problem/535/B The problem is: You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 ...
407 views

### Can counting problems have optimal substructure?

I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties: optimal substructure overlapping subproblems I stumbled upon an article which ...
218 views

### How many different trees can we form from given graph?

I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$ In this graph I want to count the sub-...
640 views

### Are counting problems the same as problems involving listing all possible combinations?

I recently tried coming up with an algorithm that uses dynamic programming for the counting variant of the change problem. Given a set of target and a set of denominations, print the number of ...
78 views

### What's wrong with this [closed]

Here's the question: Do more baby names start with "A" or "B"? Write code to count and print those two counts ("A" count, then "B" count). I then write this code down: table = new SimpleTable("baby-...
165 views

### Count arrays with size n, sum k and largest element m

I'm trying to solve pretty complex problem with combinatorics. Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K ...
1k views

### Count of distinct substrings in string inside range

Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ ...
218 views

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

How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions: no or minimal redundancy only use 1 integer variable or k independent integer variables with a ...
162 views

### Proving $\#CYCLE \in \#P$

I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\#CYCLE \in \#P$, if I could represent a distinct cycle, then I'll have a witness. I saw this question: ...
65 views

### Display Counting Algorithm

I am writing some firmware for a display that will take measurements and present them in real time on an LCD screen. I would like for the measurements to display as smoothly as possible... What I mean ...
936 views

### Counting islands in Boolean matrices

Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ ...
35 views

### Number of possible balanced binary trees [duplicate]

A tree is balanced if the subtrees of each node differ in height by at most one. How many balanced binary trees can we create from $n$ nodes?
164 views

### Finding all possible bottom-most overlapping rectangles on a table

Let's say that I'm given a $n\times n$ ($n\leq 1000$) grid (more of like a table) and I color the grid with $n^2$ rectangles, each of a different color (let's say they have colors 1 to $n^2$ for ...
400 views

### Estimating size of state space search problem

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It'...
624 views

### Sorting in place & stable in linear time

Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics- The algorithm runs in $O(n)$ time. The algorithm is stable. The algorithm sorts ...
922 views

### Counting substrings with a given number of different characters in O(N)

Given a string $S$ of length $n$, and a number $k$, count the number of substrings (regardless of their length) that contain exactly $k$ different characters. The obvious solution takes $O(n^2)$ time ...
316 views

### Find number of nodes that seperate graph to two or more subgrahps when removed individually - Find articulation points on a non-directed graph

Suppose that we have an undirected graph, and that for any two nodes there is a path from one to another. In such a graph, there might be some nodes that, if removed from the graph individually, leave ...