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
9
votes
3answers
516 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 ...
10
votes
3answers
300 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 ...
15
votes
10answers
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 ...
9
votes
0answers
119 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 ...
12
votes
6answers
758 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 ...
18
votes
8answers
1k 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 ...
12
votes
5answers
513 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 ...
11
votes
6answers
967 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, ...
26
votes
3answers
2k views

Efficient Bytewise FizzBuzz

Given the following Python "reference implementation" of non-terminating FizzBuzz: ...
0
votes
0answers
129 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 ...
15
votes
4answers
948 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 ...
15
votes
12answers
650 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 ...
-2
votes
2answers
253 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 ...
-4
votes
1answer
444 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 ...
2
votes
0answers
95 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). ...
14
votes
1answer
429 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
6answers
390 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 ...
11
votes
1answer
711 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 ...
10
votes
6answers
698 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. ...
17
votes
20answers
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. ...
13
votes
4answers
434 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 ...
11
votes
6answers
497 views

Circular Limited Sums

Challenge Let's imagine an N-tuple of integers between 0 and M inclusive, and let's call it ...
12
votes
15answers
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 ...
12
votes
14answers
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 ...
8
votes
9answers
494 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 ...
10
votes
6answers
758 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 ...
4
votes
0answers
195 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 ...
7
votes
3answers
379 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 ...
66
votes
5answers
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 ...
24
votes
2answers
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 ...
10
votes
3answers
662 views

Find the shortest pangrams from a word list

A pangram is a string that contains every letter a-z of the English alphabet, case-insensitive. (It's OK if the pangram contains ...
8
votes
16answers
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 ...
11
votes
23answers
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 ...
12
votes
9answers
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. ...
13
votes
11answers
3k views

Solve the Secretary Problem

The Secretary Problem is a famous problem described as thus: You need a new secretary You have N applicants that you can interview one at a time You are able to score each applicant after the ...
20
votes
3answers
453 views

Permutation Square Root

In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list: 2 1 4 3 represents the permutation σ such that σ(1) = 2, ...
19
votes
11answers
688 views

Maximise the squared difference

Consider a permutation of the integer values from 1 to N. E.g. this example for N = 4: <...
7
votes
3answers
486 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 ...
6
votes
3answers
518 views

Symmetric boolean functions as Zhegalkin polynomials

Let \$\mathbb{B} = \mathbb{Z}_2 = \{0, 1\}\$ be the set of booleans. A symmetric boolean function in \$n\$ arguments is a function \$f_S : \mathbb{B}^n \to \mathbb{B}\$ that checks if the number of ...
20
votes
3answers
454 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, ...
7
votes
2answers
646 views

Crack a Vigenère Cipher

A Vigenère Cipher is encrypted by repeating a keyword to be the length of the plaintext, and summing each character in that text with the corresponding letter in the plaintext modulo 26. (using A=0,B=...
12
votes
2answers
484 views

Pair Capacitors

Capacitors are notorious for being manufactured with high tolerances. This is acceptable in many cases, but some times a capacity with tight tolerances is required. A common strategy to get a capacity ...
12
votes
3answers
376 views

Books on a Shelf

I have some books and a bookshelf. I would like to put as many books on the shelf as possible but I have a rule. All dimensions of the books (height, width and depth) should form a non-increasing ...
15
votes
6answers
1k views

Real-time string matching

Task The task is to golf a real-time exact string matching algorithm of your choice. Input Two lines of text supplied on standard input, separated by a new line. The first line contains the "...
23
votes
6answers
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 ...
14
votes
4answers
1k views

Find the maximum of ax+b

You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers. Your program or function must run in expected (to the ...
47
votes
1answer
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. ...
19
votes
11answers
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 ...
21
votes
2answers
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 ...
13
votes
15answers
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 ...