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

77 questions
Filter by
Sorted by
Tagged with
464 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 ...
1k views

1 vote
254 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 ...
634 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 ... 581 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 ... 323 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 ...
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 ...
218 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 ...
823 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 ... 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 ...
541 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 ...
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, ...
2k views

### Efficient Bytewise FizzBuzz

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

### I am surely the fastest!... asymptotically [duplicate]

Background You are probably familiar with the "asymptotic time complexity" concept, which provides a way to measure how fast an algorithm runs as the input gets larger. For instance, if an ...
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 ... 657 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 ...
298 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 ...
514 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 ...
96 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). ...
690 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 ...
411 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 ...
719 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 ...
716 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. ... 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. ... 479 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 ... 524 views

### Circular Limited Sums

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