Questions tagged [restricted-complexity]
Challenges with a spec which requires all answers to meet certain time complexity restrictions. This could be specific ("Your answer must be O(n^2) where n is the number of items in the input"), or at the level of complexity classes ("Your answer must be polynomial in the number of items in the input").
83 questions
11
votes
2
answers
316
views
Fast sampling of special binary strings
We are going to define a simple little language. A word in this language is a binary string where the longest run of consecutive \$0\$s, is shorter than every (maximal) run of \$1\$s. So for example:
\...
- 103k
1
vote
2
answers
313
views
minimum line queries in logarithmic time
Input
You are given 2 positive integers, n, q, followed by q queries. the queries can be of two forms:
0 a b: add the line a*x + b. a and b are integers between -...
- 115
11
votes
16
answers
1k
views
Compute maximum excluding the current position
Given an array of integers A, the task is to output another array B of the same length so that B[i] is the maximum over A for every index that is not i. That is \$B[i] = \max_{i' \ne i} A[i']\$.
...
- 3,167
3
votes
1
answer
232
views
Output intervals for the optimal subarrays
Consider an array A of integers of length n. The k-max subarray sum asks us to find up to \$k \leq 3\$ (contiguous) non overlapping subarrays of A with maximum sum. If A is all negative then this ...
- 3,167
9
votes
1
answer
426
views
Longest Repeating Subarray (With Overlapping)
Earlier I asked about this problem on stackoverflow (link), but now I also want to see the golfiest solutions
Problem:
Given an array of arbitrary numbers, what is the longest subarray that is ...
- 191
7
votes
4
answers
862
views
Sums of Euler's totient function in sublinear time
Related.
Given a number \$n\$, Euler's totient function, \$\varphi(n)\$ is the number of integers up to \$n\$ which are coprime to \$n\$. That is, no number bigger than \$1\$ divides both of them.
For ...
- 10.9k
21
votes
11
answers
2k
views
Sums of sum of divisors in sublinear time
Given a number \$n\$, we have its sum of divisors, \$\sigma(n)\ = \sum_{d | n} {d}\$, that is, the sum of all numbers which divide \$n\$ (including \$1\$ and \$n\$). For example, \$\sigma(28) = 1 + 2 +...
- 10.9k
10
votes
2
answers
551
views
Find a string in the middle
Given two strings \$A\$ and \$B\$ with edit (Levenshtein) distance \$x\$, find a third string with edit distance \$a\$ to \$A\$ and edit distance \$b\$ to \$B\$ so that \$a+b=x\$ and \$a=int(x/2)\$ (...
- 3,167
10
votes
3
answers
398
views
Representing a number as an unordered list of smaller numbers
Suppose we want to encode a large integer \$x\$ as a list of words in such a way that the decoder can recover \$x\$ regardless of the order in which the words are received. Using lists of length \$k\$ ...
- 871
12
votes
17
answers
2k
views
Compute cumulative means efficiently
Consider a sorted array of positive floating point numbers such as:
input = [0.22, 2.88, 6.35, 7.17, 9.15]
For each integer \$i\$ from 1 up to the last value in ...
- 3,167
13
votes
14
answers
790
views
Generate a permutation from the high-water marks
Given a permutation, we can define its high-water marks as the indices in which its cumulative maximum increases, or, equivalently, indices with values bigger than all previous values.
For example, ...
- 10.9k
8
votes
3
answers
444
views
Injectively saturate bit strings
It can be easily proven using Hall's marriage theorem that given fixed \$n\$ and \$k<n/2\$, there is an injective (one-to-one) function from all \$n\$-bit strings with \$k\$ ones to \$n\$-bit ...
- 4,749
7
votes
3
answers
498
views
Minimum Cut finder
Write a program that takes an undirected graph and finds the minimum cut, i.e., the set of edges that, if removed, would disconnect the graph into two or more connected components. The program should ...
user116868
12
votes
11
answers
838
views
Find Sub-matrix with matched cell 1
You are given a matrix of size m x n where each cell can contain either 1 or 0. You need to find the largest square submatrix that contains only 1's. The output should be the area of the largest ...
user116868
9
votes
9
answers
924
views
Find the length of the longest substring with all different characters in O(n) time
Let's solve the same task as in this challenge but faster!
Input: a non-empty string containing letters a-z
Output: the length of a longest (contiguous) substring in which all letters are different
...
- 14.1k