Questions tagged [counting]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
19 views

Build a histogram from a very large data sample

I want to calculate a histogram from an array of size N. N is very large. I know 2 ways to do so: The naive approach is to ...
3
votes
1answer
4k 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 ...
3
votes
2answers
105 views

Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?

I am trying to find the fastest algorithm to find all the possible paths of length $N$ from a given node in a directed graph. My solution is to do a modification of breadth first search from the ...
3
votes
1answer
22 views

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$

Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$. I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]...
-1
votes
3answers
74 views

Can approximation help find the exact answer?

Lets assume we have an array with 100 numbers and we want to find how many '1's there are. Best solution will be reading every numbers and counting. Now we get a hint that there are 50,51 or 52 '1' in ...
7
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
53 views

On FPTAS and many one parsimonious reductions

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have? If $\Pi_2$ has an ...
1
vote
1answer
83 views

How to find the Big-O for finding combinations of balanced parentheses?

Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be: ...
0
votes
1answer
160 views
0
votes
0answers
46 views

Counting number of apples in an apple tree with given number of layers

This problem comes from a competitive programming question, and it seems to require dynamic programming. There are several layers of apples arranged in a formation with each apple having a value ...
0
votes
1answer
57 views

Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq ...
0
votes
0answers
14 views

Calculating Time Complexity of Algorithm Using Incrementor Variable [duplicate]

I am trying to calculate the time complexity of an algorithm using n in the code below. I have a working solution to a coding challenge to sort a stack using only ...
2
votes
1answer
65 views

Number of ways painting graph in two colors, such that two nodes of same color are linked by edge

We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must ...
3
votes
0answers
36 views

Does $P=PP$ or $P=PSPACE$ have consequences for algebraic class problem $VP=VNP$?

Deciding majority of counting problem is $PP$ class. Is there any relation between $PP$ and $VNP$ and is there consequence of $P=PP$ or $P=PSPACE$ to $VP=VNP$? Is there a way to show $\#P$ is in $FP^...
1
vote
2answers
91 views

Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems

I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an ...
2
votes
1answer
40 views

Estimation of the number of solutions by Counting

This is a question from a quantum computation textbook. Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
2
votes
2answers
63 views

Prove that this language is NP-Hard

Given $$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$ prove that $\mathrm{\#3SAT}$ is NP-Hard. I am currently stuck with ...
-2
votes
1answer
314 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 ...
3
votes
1answer
43 views

Why does not valiant's reduction show NP=RP?

Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\#SAT$. We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in ...
3
votes
1answer
50 views

The expectation of the total number of pairs of keys in a hash table that collide using universal hashing

I am reading CLRS relating to perfect hashing. When computing the $$ \mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}] $$ where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
1
vote
1answer
473 views

How many ways to express N as sum of 2, 3 and 5?

I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7: N = 5 + 2 N = 2 + 5 N = 2 + 2 + 3 N = 2 + 3 + 2 N = 3 + 2 + 2 But most of I found on the Internet that the ...
0
votes
1answer
289 views

Limitations of DFA [duplicate]

In this link it is mentioned: A DFA is not powerful enough to recognize many context-free languages because a DFA can't count. But counting is not enough -- consider a language of ...
0
votes
1answer
66 views

Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
0
votes
0answers
11 views

List maximum number of three-sets

Suppose i'm given with pairs component-quantity. I need to list maximum number of possible three-sets. {AA}, {BB}, {C}, {D} => {ABC},{ABD}. To list two-sets ...
0
votes
1answer
36 views

Can someone give me the definition of #Monotone-2SAT?

In the decision problem, I set all variables to true and see if the formula is satisfiable. My question is because I do not understand how there can be multiple solutions, though all variables are ...
1
vote
1answer
97 views

Find total count of all paths starting from a fixed vertex to all other vertexes of the graph

Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e. $$ \text{#(paths from 1 to 2)}+\text{#(...
2
votes
0answers
112 views

Min no.of operations required to convert an array to which it should contain elements of equal frequency

I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
1
vote
1answer
24 views

Is there an FPRAS for the number of min st cuts in general graphs?

Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get ...
1
vote
0answers
34 views

Count paths in matrix that visit each number exactly once [duplicate]

Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$. We want to count the number of paths that start ...
2
votes
2answers
257 views

Count-min sketch

I don't understand the use case of count min sketch. Based on Count–min sketch, it says "serves as a frequency table of events in a stream of data.". If I know there are N types of events, why can't ...
3
votes
1answer
331 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 ...
0
votes
0answers
26 views

Find xor sum of all pairs raised to power of 3

We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} (...
1
vote
0answers
33 views

Counting on a matrix

I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$. If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are ...
1
vote
1answer
38 views

Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it

Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the ...
2
votes
1answer
412 views

How to find all topological sortings of a special DAG in O(N^2)

I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG. https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum ...
0
votes
0answers
46 views

Count submatrices with only zeros for each element of the matrix

Let's say we have given matrix of size $N \cdot M$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. ...
4
votes
3answers
157 views

Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
4
votes
2answers
75 views

Count numbers less than $x$ co-prime to $p$

We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$. I know that we can solve the problem in $O(x\log x)$ with iterating over all ...
2
votes
1answer
35 views

Count number of the ways to fill a N-lengthed binary string

From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
-1
votes
1answer
78 views

Counting (enumerating) minimal solutions of a dual horn formula

Is there an efficient algorithm ("does not necessarily have to be a polynomial time algorithm") to compute all "minimal" solutions for a Dual Horn formula (conjunction of clauses where each clause ...
2
votes
0answers
73 views

Counting subarrays where each number either doesn't occur or occurs odd number of times

We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times. ...
0
votes
2answers
65 views

Why it is not $O(m)$ but $O(\log m)$?

I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2. Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$. ...
2
votes
3answers
1k views

Computing a histogram with the number of extant values not known in advance

(This may be more fitting for CSTheory, I'm not sure.) I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for ...
0
votes
2answers
101 views

Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) ...
3
votes
0answers
31 views

Number of distinct single-assignment forms with $j$ binary function calls?

Given $n$ inputs and $k$ outputs and $j$ identical binary function calls to $g$, how many possible distinct single-assignment forms are there? The only assumption made about $g$ is that if $a = c \...
0
votes
1answer
117 views

How to count number of 1s of the first k positions in a bitset (bitmap)?

Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$. Output: the total number of 1s in the first $k$ position of $b$. Obviously it can be done in $...
1
vote
1answer
153 views

Counting solutions of a particular type in HORN SAT

I am interested in counting the number of solutions of a particular type (say #) in HORN SAT. I have 2 questions concerning the same. Suppose we have a HORN SAT -: $(x_1) \land (x_2 \implies x_1)$, ...
0
votes
1answer
75 views

Modified Counting Inversions problem using divide and conquer

Given an array $A$, find the number of pairs $(i, j)$, such that $ i > j$ and $A[i] \ge A[j]$. This is a modified version of the famous problem of Counting Inversions, only in this version it ...
9
votes
2answers
873 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$ ...
3
votes
0answers
89 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 ...