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").
82 questions
1
vote
2
answers
312
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
231
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
424
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
858
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
550
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
397
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
789
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
441
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
495
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
837
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
923
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
12
votes
10
answers
1k
views
Maximum of outer product of integer vectors (in linear time)
Introduction
Our goal is to efficiently find the maximum of a large amount of (redundant) data.
We define the outer product of vectors \$A\$ and \$B\$ as a matrix containing the products of all ...
- 221
10
votes
6
answers
818
views
CGAC2022 Day 13: Santa's gift and the laser lock, Part 2
Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
You successfully route the laser into the sensor, but nothing happens.
"What?" Frustrated, you flip the ...
- 79.3k
12
votes
3
answers
569
views
><> numbers metagolf
I struggle to easily encode big numbers in ><>. If only there was a program that could find the best way for me?
What is ><>
...
- 14.4k
10
votes
9
answers
465
views
Sample from the discrete triangular distribution
Given an integer n >= 1 as input, output a sample from the discrete triangular distribution over the integers k, for ...
- 4,192
8
votes
1
answer
570
views
Next Special String
Special String
We call a binary string \$S\$ of length \$N\$ special if :
substring \$S[0:i+1]\$ is lexicographically strictly smaller than substring \$S[i+1:N]\$ for \$ 0\leq i\leq N-2\$,
Note: \$ S[...
- 619
1
vote
1
answer
296
views
Implement the slowest possible sorting algorithm that retains a fast best case [closed]
I have recently been on a quest to create really really slow sorting algorithms that make Bogosort seem like it is the best.
The task is simple: Sort an array of integers in as long average time as ...
- 27
18
votes
3
answers
744
views
Find a factorial with n trailing zeros, quickly
Problem
A fact you may have noticed about factorials is that as \$n\$ gets larger \$n!\$ will have an increasing number of \$0\$s at the end of it's base \$10\$ representation. In fact this is true ...
- 103k
2
votes
1
answer
1k
views
An Scalable Event Scheduler That Can Handle Billions of Events [closed]
The event scheduler is a recurrent theme in event-driven architectures: something triggers an event that needs to be checked in the future one or more times. I has particular use in trading where you ...
user108147
10
votes
3
answers
650
views
rank and unrank arrays of integers
Consider all arrays of \$\ell\$ non-negative integers in the range \$0,\dots,m\$. Consider all such arrays whose sum is exactly \$s\$. We can list those in lexicographic order and assign an ...
user7467
9
votes
3
answers
391
views
How many dominoes can you fit here?
Much harder than Can this pattern be made with dominoes?
Challenge
A grid of width \$w\$ and height \$h\$ is given, filled with 1s and 0s. You can place a domino somewhere on the grid only if both ...
- 79.3k
14
votes
10
answers
3k
views
Project Euler 1: Multiples in constant time
The purpose of this challenge is to solve the original first Project Euler problem, but as the title suggests in constant time (with respect to the size of the interval).
Find the sum of all the ...
- 697
12
votes
0
answers
310
views
NP-complete reduction: (grid-)Hamiltonian circuit
Background
Hamiltonian circuit problem is a decision problem which asks whether a given graph has a Hamiltonian circuit, i.e. a cycle that visits every vertex exactly once. This problem is one of the ...
- 79.3k
16
votes
6
answers
1k
views
Continuous knapsack but fast
The input for the continuous knapsack problem is as follows.
For each item 1...n we are given a positive weight and profit. Overall we are also given a positive capacity which is the maximum weight ...
user7467
19
votes
8
answers
2k
views
Sum of set bits from 1 to n
Given an integer \$ n \$ \$ (n \ge 1) \$, return/output the total number of set bits between \$ 1 \$ and \$ n \$ inclusive. To make the problem more interesting, your solution must run with a time ...
- 23.4k
12
votes
5
answers
609
views
Subarrays With At Least N Distinct Integers
Given a sequence of integers and an integer N, output the number of contiguous subsequences that contain at least N distinct ...
- 459
12
votes
6
answers
1k
views
Three, Three, No
Given a non-empty sequence of non-negative integers, output any permutation of it in which no two adjacent elements have a sum that is divisible by 3. If it is impossible, either crash the program, ...
- 459
28
votes
3
answers
2k
views
Efficient Bytewise FizzBuzz
Given the following Python "reference implementation" of non-terminating FizzBuzz:
...
- 479
16
votes
4
answers
1k
views
Code golf edit distance 2
The edit distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other.
This task is simply to write ...
user9207
16
votes
12
answers
770
views
Combinations of stepwise increasing integers
Working on something in probability theory, I stumbled across another combinatorical exercise. These are always fun to solve, searching for intelligent approaches. Of course, one can use brute force ...
- 161
-4
votes
2
answers
349
views
A really inefficient calculator [closed]
Challenge: Add two numbers. In O(n^m) time, where n and m are the two numbers given. Sleeping, or your language equivalent, is not allowed.
Input: Two integers, separated by a space.
Output: The sum ...
- 15
-6
votes
1
answer
580
views
Write the shortest O(n^2) sorting algorithm [closed]
Write a sorting algorithm for a list of integers that has an average performance of O(n^2).
This is code-golf, so the shortest code in bytes wins.
RULES:
The characters wasted for the declaration of ...
- 531
1
vote
0
answers
109
views
Finding row wise sum of transpose of hv-convex binary matrix [closed]
I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).
...
- 119
18
votes
1
answer
788
views
Solve Subset-Sum in polynomial time (...if P = NP)
Shocking news: Dr. Mad J Scientist has released a proof of P = NP to the world. But the proof is nonconstructive, and she's keeping the algorithm to herself.
Worry not. Without even looking at her ...
- 331
3
votes
6
answers
490
views
Let's Play some ProSet! [duplicate]
ProSet is a classic card game that is played normally with 63 cards. One card has 6 colored dots on it, like below
The rest of the cards are missing some of these 6 dots, but each card has at least 1 ...
- 2,635
11
votes
1
answer
765
views
Polite Near-Sighted Drunk Bot on a Minefield
As the title may suggest, this problem is semi-inspired by the Polite Near-Sighted Drunk Bot by @N.P.
Our poor bot is placed on a cartesian grid at the origin, and after each minute, it moves 1 unit ...
- 2,635
11
votes
6
answers
792
views
Find the sum of closest distances
For this task your code should take two sorted arrays of integers X and Y as input. It should compute the sum of the absolute distances between each integer in X and its closest number in Y.
...
user9207
18
votes
20
answers
3k
views
Give a permutation with no two consecutive integers next to each other
Challenge
Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers (integers with absolute difference 1) are next to each other.
...
user9207
15
votes
4
answers
560
views
Generalized Gray codes
Input: An array I of k positive integers. The integers will be no larger than 100 and k ≤ 100.
Output: Your code must output all possible arrays O of non-negative integers of length k with the ...
user9207
11
votes
6
answers
617
views
Circular Limited Sums
Challenge
Let's imagine an N-tuple of integers between 0 and M inclusive, and let's call it ...
- 79.3k
13
votes
15
answers
1k
views
Binning in time
The task in this challenge is to put elements of an array into time bins. The input will be a non-decreasing array of positive integers representing the time of events, and an integer which represents ...
user9206
13
votes
14
answers
2k
views
Put an array into bins
In this simple challenge you are given an input array L of non-negative integers and a number of bins b greater than 0 but no ...
user9206
8
votes
9
answers
628
views
Make sets disjoint without emptying them
Suppose you have a set of sets of integers. It's possible that some of the sets will overlap (i.e. sharing elements). You could get rid of the overlaps by deleting elements from the sets, but then ...
- 223
9
votes
6
answers
972
views
Output all distinct permutations of a vector
Challenge:
Output all distinct permutations of a, potentially long, list of positive integers. You may assume that the vector has less than 1,000 numbers when testing, but the process should in ...
- 46.8k
3
votes
0
answers
228
views
Those annoying grasshoppers [closed]
The problem #6 of IMO 2009 reads:
Let a 1, a 2, a 3, ..., a n, be distinct positive integers and let T be a set of n-1positive integers not containing a 1+a 2+a 3+...+a n, A grasshopper is to ...
- 207
8
votes
4
answers
490
views
Quickly Prove Me Wrong!
Introduction
This is the evolution of this previous challenge which was about checking satisfieability of normal formulae in conjunctive normal form (CNF). However, this problem is NP-complete and ...
- 3,463
69
votes
6
answers
5k
views
Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one
Write a program (or function) that exhibits four common big O time complexities depending on how it is run. In any form it takes in a positive integer N which you may assume is less than 231.
When the ...
- 90.7k