Questions tagged [counting]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
79 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-...
2
votes
3answers
261 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 ...
9
votes
2answers
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$ ...
0
votes
1answer
235 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 ...
0
votes
1answer
208 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: ...
-1
votes
1answer
67 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 ...
9
votes
2answers
1k 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$ ...
0
votes
0answers
44 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?
0
votes
0answers
170 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 ...
2
votes
1answer
2k 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'...
5
votes
0answers
695 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 ...
5
votes
2answers
1k 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 ...
2
votes
1answer
352 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 ...
0
votes
1answer
65 views

Finding alternative way of combinatorial counting

The question is related to databases: There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are? I thought if any one of the $(n-...
1
vote
0answers
98 views

What are widely-used, practical applications to come from the study #P problems?

When, beyond theoretical exercises, do we care how many solutions we can find for something? I had an analogous question for TMs before - why is it useful to study machines that can only deliver ...
2
votes
1answer
143 views

Computing counts of combinations (?)

I'm not sure what terminology to use. Here is some input: John has items: A B D Peter has items: A C D And I want to produce such a table, that would count the #...
8
votes
3answers
2k views

Finding all solutions to an integer linear programming (ILP) problem

My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this ...
1
vote
0answers
82 views

Count all possible 2-3-monotone sequences

Let $N \leq 1000$, a 2-3-monotone sequence $s$ of length $N$ is defined as: $s_i < s_{i+2}$, for $1 \leq i \leq N-2$ $s_i < s_{i+3}$, for $1 \leq i \leq N-3$ $s_i \in \{1,\dots, N\}$ Given $N$...
1
vote
3answers
78 views

Count elements in the real world in constant time by weighing them

I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out ...
-1
votes
1answer
1k views

DFS for all possible walks from a source to a destination with exactly k edges

Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk. My question is that, say we have a DAG (...
-2
votes
2answers
698 views

Count all numbers up to X that are divisible by at least two of their digits

I want to count how may numbers are there in range [1,X] which are divisible by at least two of their digits, different and >1. I found a sequence on OEIS, but this will take lot of time to generate ...
2
votes
1answer
76 views

Counting specific subgraphs

For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions: H.V = G.V (The subgraph will containt all the original graph nodes) H is connected (Note: ...
0
votes
0answers
34 views

Complexity of Self avoiding walks in unary

In this paper http://eccc.hpi-web.de/report/2001/061/ by Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda the complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and ...
5
votes
1answer
6k views

How to calculate an accurate estimated reading time of text?

I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the ...
29
votes
5answers
6k views

Boolean search explained

My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding ...
3
votes
1answer
151 views

Number of states in an AND-OR DAG

Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND ...
14
votes
1answer
582 views

Why is the counting variant of a hard decision problem not automatically hard?

It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a ...
-2
votes
1answer
1k views

Count number of automata with 3 states and alphabet of size 2

How many different finite automata are there that have 3 states $q_0$, $q_1$ and $q_3$, have an alphabet of size 2, and where $q_0$ is starting state?
1
vote
1answer
95 views

Count all pairs of x,y such as x + y = c && x XOR y = d

Given two decimals $c$ and $d$; $1 \le c,d \le 10^{12}$. Count all pairs of $x$ and $y$ that satisfy the following statements: $$ x+y = c\\ x \text{ XOR } y = d $$ Killed already a day still can't ...
5
votes
2answers
347 views

Finding the number of square prefixes of a string in linear time

Let square denote a concatenation of two identical, nonempty strings. Given a string $w$, devise an $O(|w|)$ algorithm that counts the number of prefixes of $w$ that are squares. My initial idea ...
2
votes
0answers
73 views

Complexity class of a counting problem

Consider the following inequalities: $\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$ $\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$ $x_{ij} \ge 0 \;\;\; i,j=1,...,n$ $y_i \in \{0,1,2\} \,\,\,\, i=1,...,...
3
votes
1answer
340 views

The most efficient algorithm for computing cardinality of sumset

Let A and B be two finite non-empty sets of positive integers. Their sumset is the set of all possible sums a + b where a is from A and b is from B. For example, if A = {1, 2} and B = {2, 3, 6} then A ...
1
vote
1answer
1k views

How do I find the number of inversions using a red black tree?

I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node ...
2
votes
1answer
7k views

Seating arrangement problem

$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$ Each professor has people they like to sit next to and people they do not want to sit next ...
2
votes
1answer
993 views

Count the number of Euler PATHs in directed graph?

I would like to find all Euler PATHs in a directed graph. Counting (instead of finding) all the Euler PATHs is sufficient. Circuits are not good for me, only Paths. I am doing a problem, that I have ...
1
vote
2answers
226 views

Is there a known, fast algorithm for counting all subsets that sum to below a certain number?

I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum: Given a set of integers, $S$, and a target number, $n$, what is the ...
3
votes
1answer
160 views

Counting words that satisfy SAT-like constraints with BDDs

I have the following #P-complete problem: Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $*$, find the number of strings $s$ with ...
0
votes
0answers
480 views

Number of paths between two nodes in mesh topology

Is there any way to find generalized formula to calculate the number of paths of different length between two nodes of the network connected in mesh topology, given that the network contains n nodes?
1
vote
1answer
154 views

fastest counting of nested loops

I need to find out the fastest way to count nested loops. I am adding 3 numbers , the final number is wanted result. For better explanation here is example ...
-1
votes
2answers
2k views

number of subsets where GCD equals to X

The original statement for this problem can be found here This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD ...
3
votes
2answers
239 views

Counting the number of tree when the set of the subtrees is given

There are a set $A$ of trees. There is another set $B$ of trees that is the collection of all possible subtrees of the trees in $A$. I don't have $A$ but only have $B$, and I need to figure out the ...
2
votes
1answer
146 views

Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization

What is the best algorithm for computing the number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization $n=p_1^{a_1}p_2^{a_2} \ldots p_i^{a_i}$? ...
4
votes
1answer
278 views

Counting the solutions to a restricted 0-1 knapsack problem

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ : Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms. Output: ...
-1
votes
1answer
1k views

count number of different DFS tree of specific graph - ladder

It is given graph. It isn't ordinary graph, it is ladder. We say that our ladder has order $n$, because of number of nodes. Look at picture: My problem is: Let's start DFS on node number $1$. How ...
2
votes
1answer
2k views

counting binary, with moving position (turing machine)

I'm trying to make a turing machine that will take in a binary string as input x and output the binary representation of the length of x. So M(0110) returns 100, M(1010101010) returns 1010, ect. It ...
0
votes
0answers
381 views

Possible paths in pipe network, without loops and with some one-way valves

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit I have to ...
2
votes
1answer
91 views

Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example: ...
-1
votes
1answer
2k views

Can a computer count to infinity? [closed]

So, could a computer count to infinity assuming it was a super computer and had near unlimited amounts of ram and hard drive/solid state drive storage? I am being serious when I ask this. [This is ...
3
votes
1answer
566 views

Proof of $P^{\text{#}P} = P^{PP}$

I was reading this article on the complexity class $PP$. In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please ...
2
votes
2answers
481 views

What are the k characters which make the most complete words?

Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ ...