# Questions tagged [counting]

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

134 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
22 views

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 ...
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 ...
36 views

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 ...
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 ...
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 ...
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. ...
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: ...
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 ...
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 ...
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 ...
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. ...
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$. ...
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 ...
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) ...
31 views

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)$, ...
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 ...
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$ ...