Skip to main content

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").

Filter by
Sorted by
Tagged with
14 votes
6 answers
909 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 ...
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 votes
1 answer
193 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 ...
8 votes
1 answer
351 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 ...
20 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 +...
6 votes
4 answers
562 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 votes
2 answers
482 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)\$ (...
7 votes
4 answers
430 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 ...
67 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 ...
13 votes
14 answers
614 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, ...
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 ...
10 votes
3 answers
329 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\$ ...
8 votes
3 answers
365 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 ...
5 votes
3 answers
346 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 ...
11 votes
9 answers
644 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 ...
9 votes
9 answers
348 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 ...
12 votes
10 answers
914 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 ...
10 votes
9 answers
817 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 ...
11 votes
3 answers
803 views

Sort some apples!

Problem Imagine 7 buckets lined up in a row. Each bucket can contain at most 2 apples. There are 13 apples labeled 1 through 13. They are distributed among the 7 buckets. For example, ...
12 votes
3 answers
480 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 ><> ...
10 votes
6 answers
741 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 ...
19 votes
11 answers
2k views

Random Golf of the Day #3: Integer Partitions

About the Series First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You ...
9 votes
3 answers
584 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 ...
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 ...
8 votes
1 answer
420 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: \$ ...
48 votes
1 answer
5k views

Longest common substring in linear time

This challenge is about writing code to solve the following problem. Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties. ...
1 vote
1 answer
258 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 ...
18 votes
3 answers
644 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 ...
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 ...
8 votes
2 answers
4k views

Quickly find length of n-th term of the look-and-say sequence

The look and say sequence is an example of a run length encoding sequence. To get the next term of the sequence one groups the sequence into runs of the same number, each group in the next term then ...
14 votes
24 answers
4k views

Merge two sorted lists

Merge Sort In this challenge, you will implement the merge subroutine of merge sort. Specifically, you must create a function or program or verb or similar which takes two lists, each sorted in ...
21 votes
2 answers
1k views

Book Stack Sort

When stacking books you usually want to put the largest ones at the bottom and the smallest ones at the top. However, my latent OCD makes me feel very uneasy if I've got two books where one is shorter ...
9 votes
3 answers
326 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 ...
18 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 ...
15 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 ...
11 votes
0 answers
228 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 ...
10 votes
6 answers
844 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 ...
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, ...
12 votes
5 answers
542 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 ...
28 votes
3 answers
2k views

Efficient Bytewise FizzBuzz

Given the following Python "reference implementation" of non-terminating FizzBuzz: ...
11 votes
6 answers
528 views

Circular Limited Sums

Challenge Let's imagine an N-tuple of integers between 0 and M inclusive, and let's call it ...
10 votes
3 answers
399 views

Unfolding an integer

Given the functions L: (x, y) => (2x - y, y) R: (x, y) => (x, 2y - x) and a number N generate a minimal sequence of ...
23 votes
6 answers
5k views

Chinese Remainder Theorem

The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in ...
16 votes
12 answers
658 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 ...
12 votes
23 answers
2k views

Find the positive divisors!

Definition A number is positive if it is greater than zero. A number (A) is the divisor of another number (B) if ...
18 votes
1 answer
699 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 ...
-3 votes
2 answers
304 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 ...
12 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 ...
8 votes
16 answers
3k views

Check if 2 arrays contain the same element

Write a program which will take for input 2 integer arrays and return a truthy value if there exists an element which is present in both of arrays, or a falsy one otherwise. The obvious solution to ...
19 votes
3 answers
489 views

One goes up, the other comes down

Introduction In this challenge, your task is to decide whether a given sequence of numbers can be separated into two subsequences, one of which is increasing, and the other decreasing. As an example, ...