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

79 questions
Filter by
Sorted by
Tagged with
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 ...
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']$. ...
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 ...
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 ...
2k views

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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
2k views

### Efficient Bytewise FizzBuzz

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

### Circular Limited Sums

Challenge Let's imagine an N-tuple of integers between 0 and M inclusive, and let's call it ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...