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
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 ...
xnor's user avatar
  • 145k
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 ...
Martin Ender's user avatar
5 votes
7 answers
1k views

Return the first N primes

With a twist; your algorithm has to be less complex than O(X2) where X is the Nth prime. Your solution post should include the character count and the theoretical complexity in terms of X (or N, which ...
KeithS's user avatar
  • 211
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. ...
user avatar
18 votes
1 answer
698 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 ...
Lopsy's user avatar
  • 331
17 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. ...
user avatar
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 ...
user avatar
7 votes
3 answers
538 views

Convolve integers in subquadratic time

An linear discrete convolution is an operation that turns two vectors of numbers into a third vector of numbers by multiplying elements inside-out. Formally, for two vectors ...
FUZxxl's user avatar
  • 10.1k
25 votes
2 answers
1k views

Write an Incident tokeniser

Background Incident is a fairly unusual programming language, in that its list of tokens is not predetermined, but rather inferred from the input. As such, tokenising an Incident program can be ...
user avatar
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 ...
Martin Ender's user avatar
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 +...
Command Master's user avatar
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, ...
Zgarb's user avatar
  • 42.6k
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 ...
isaacg's user avatar
  • 42k
13 votes
15 answers
3k views

Pick the longest stick

You are a young programming geek living with your 2 other best friends. Every week, one of you has to do all the chores of the house and you decide whose turn it is by picking a stick. The one who ...
Optimizer's user avatar
  • 26.5k
13 votes
4 answers
489 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 ...
user avatar
12 votes
9 answers
1k views

A classic sorting code-golf question

This is a code-golf question. Input A list of non-negative integers in whatever format is the most convenient. Output The same list in sorted order in whatever format is the most convenient. ...
user avatar
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 ...
Parcly Taxel's user avatar
  • 3,737
6 votes
13 answers
895 views

Generate the list [1, 0, -1, 0, 1, 0, -1, 0, ...] [closed]

In the spirit of a question on math.se: given an integer n, return the integer in position n of the sequence [1, 0, -1, 0, 1, 0, ...
Snowball's user avatar
  • 169
6 votes
0 answers
785 views

Stable positive/negative separation [closed]

From SO. You are given an array with positive and negative integers. Write a function to change the elements order in the array such that negative integers are at the beginning, the positive integers ...
Alexandru's user avatar
  • 6,154