Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

Questions tagged [fastest-algorithm]

Ask Question

Fastest-algorithm competitions are won by the answer with the smallest asymptotic time complexity. For challenges based on actual runtime, use [fastest-code] instead.

78 questions
Newest Active Bountied Unanswered
Filter by
Sorted by
Tagged with
3 votes
7 answers
483 views

Given two non-empty sets of points \$P,T = \{(x,y)\ |\ x,y \in \mathbb{Z} \}\$, find the point \$p \in P\$ such that it is the "most isolated" from all points in \$T\$. The "most ...
bigyihsuan's user avatar
  • 11.4k
5 votes
1 answer
376 views

This is a joint post with https://puzzling.stackexchange.com/questions/126255/dishonest-dungeon-staff You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal ...
Fluorine's user avatar
  • 151
2 votes
4 answers
742 views

Given an \$n \times n\$ matrix of integers, The task is to find the optimal dividing line that maximizes the sum of the integers on the same side as the top left corner. The dividing line should be ...
Simd's user avatar
  • 3,167
1 vote
1 answer
629 views

Consider an \$n \times n\$ grid of integers which is part of an infinite grid. The top left coordinate of the \$n \times n\$ grid of integers is \$(0, 0)\$. The task is to find a circle which when ...
Simd's user avatar
  • 3,167
4 votes
2 answers
414 views

For this problem you are given an \$n \times n\$ matrix of integers. The task is to find a pentagon in the matrix with maximum sum. The pentagon must include part (or all) of the x and y axes as two ...
Simd's user avatar
  • 3,167
0 votes
2 answers
292 views

Challenge This challenge is based on the domino effect: Initially, each domino is located on one straight line and is in a vertical state. It can be dropped either to the left along the same straight ...
Michael's user avatar
  • 11
4 votes
1 answer
678 views

Consider an \$n \times n\$ grid of integers. The task is to draw a straight line across the grid so that the part that includes the top left corner sums to the largest number possible. Here is a ...
Simd's user avatar
  • 3,167
7 votes
4 answers
768 views

You are given an array A of non-negative integers. You can pick any non-empty subset, S from the array A. The score of a subset S is the sum of the elements in S raised to the power of K, i.e. for a ...
user avatar
1 vote
2 answers
618 views

Input: an array of length \$n\$ containing integers in the range \$0\$ to \$2n\$. For each integer \$x\$ in the array, compute the number of integers that occur before \$x\$ that are no larger than \$...
Simd's user avatar
  • 3,167
7 votes
3 answers
641 views

I have string \$s\$ of length \$n\$ and some constant integer \$k\$ which is at most \$n\$. Give the fastest algorithm to sample a random string with Levenshtein distance \$k\$ from \$s\$ uniformly. ...
Simd's user avatar
  • 3,167
11 votes
11 answers
1k views

Fast and Golfiest Robbers Thread Welcome to the first season of Fast and Golfiest, a cops-and-robbers challenge! I designed this challenge to encourage competitive coding for efficiency (fastest ...
Shiran Yuan's user avatar
  • 610
18 votes
15 answers
2k views

Fast and Golfiest Cops Thread Welcome to the first season of Fast and Golfiest, a cops-and-robbers challenge! I designed this challenge to encourage competitive coding for efficiency (fastest ...
Shiran Yuan's user avatar
  • 610
7 votes
6 answers
495 views

I have a follow-up question here from my previous question on Math SE. I am lazy enough to explain the content again, so I have used a paraphraser to explain it below: I was considering arbitrary ...
aitzazisstuffed's user avatar
  • 1,970
7 votes
3 answers
495 views

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 ...
user avatar
9 votes
3 answers
698 views

Introduction The \$RADD(n)\$ operation is defined as the sum of \$n + [\$ the number whose decimal representation are the decimal digits of \$n\$ in reverse order \$]\$, see A004086. After reversal, ...
Hugo Pfoertner's user avatar
  • 711
16 votes
1 answer
400 views

Given an array of \$n\$ positive integers we will say its self-sum order is the number of ways to add elements from it to make \$n\$. We will count ways as distinct up to associativity. So \$1+(2+3)\$...
Wheat Wizard's user avatar
  • 103k
2 votes
0 answers
437 views

It is known that any natural number can be decomposed into the sum of three triangular numbers (assuming 0 is triangular), according to Fermat's Polygonal Number Theorem. Your task is to come up with ...
Study's user avatar
  • 45
7 votes
1 answer
268 views

In this question I asked you to determine if a run ascending list could be made. It was code-golf so naturally most the answers are very slow. But what if we want it to be fast. In this challenge I ...
Wheat Wizard's user avatar
  • 103k
7 votes
2 answers
525 views

Given a list of N lists, each containing M positive integers, and a separate list of M positive integers (target values), return a list of N scalars (integers with a value of 0 or more) that ...
drmosley's user avatar
  • 757
10 votes
1 answer
416 views

Consider a NxN pixel grid with up to M objects drawn on it, either squares or diamonds: square    diamond The objects may overlap, so recognition is hard. The task is to give the minimal possible ...
Hans-Peter Stricker's user avatar
  • 201
-2 votes
1 answer
222 views

Challenge Given a positive integer, find the fastest way to iterate over its digits. Bytecode size doesn't matter as much as speed of execution. Examples For 6875, the program would output ...
Paul Razvan Berg's user avatar
  • 105
10 votes
5 answers
733 views

This challenge is about the following variant of edit distance. Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter ...
user avatar
12 votes
1 answer
411 views

Leon's story Leon is a professional sling shooter and he comes to a shooting range everyday to practice. A casual target is not a challenge for him anymore so before shooting he first covers the ...
Elgirhath's user avatar
  • 740
13 votes
3 answers
636 views

With all the gyms closed down with the COVID-19 situation, we have to exercise with the weight we have lying around at home. The problem is, we have a small selection of plates at varying weights, and ...
Josue Espinosa's user avatar
  • 233
1 vote
0 answers
189 views

A directed graph G is given with Vertices V and Edges E, representing train stations and unidirectional train routes respectively. Trains of different train numbers move in between pairs of Vertices ...
Viswa's user avatar
  • 173
13 votes
1 answer
471 views

Problem description Vertices \$V\$ of directed graph \$G=(V,E)\$ represent gossipping ladies; edge \$(u,v) \in E\$ signifies that lady \$u\$ knows of lady \$v\$ (which does not imply that lady \$v\$ ...
kyrill's user avatar
  • 615
4 votes
2 answers
277 views

Let me know if this task has already been posed. I haven't found it when I looked. Input master sequence \$\ X = x_1\dots x_n\$: sequence of characters, eg. \$\rm international\$ subsequence \$\ Y = ...
kyrill's user avatar
  • 615
3 votes
1 answer
537 views

Gaussian integer is a complex number in the form \$x+yi\$, where \$x,y\$ are integer and \$i^2=-1\$. The task is to perform such operation for Gaussian integers \$a,b\$, that \$a=q \cdot b+r\$ and \$|...
Alexey Burdin's user avatar
  • 1,268
5 votes
2 answers
608 views

Challenge Given an array of positive integers and a threshold, the algorithm should output a set of consecutive-element-groupings (subarrays) such that each group/subarray has a sum greater than the ...
Mike Ponemariko's user avatar
  • 51
11 votes
1 answer
344 views

In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use ...
nick012000's user avatar
  • 211
2 votes
0 answers
113 views

Problem: We have a two dimensional matrix of positive integer cells. On each turn any non-zero cell with a neighbor (top/bottom/left/right) of zero decreases by 1. We want count to the number of non-...
LFA's user avatar
  • 21
-7 votes
4 answers
344 views

Input A single integer in your language's preferred format, e.g int or an array of digits are all acceptable. Output A truthy or falsely value, depending on ...
Geza Kerecsenyi's user avatar
  • 2,321
23 votes
23 answers
4k views

Upside-Down Pyramid Addition is the process of taking a list of numbers and consecutively adding them together until you reach one number. When given the numbers ...
Whimpers's user avatar
  • 355
6 votes
0 answers
364 views

You're tasked with writing an algorithm to efficiently estimate cost of solving an Eni-Puzzle from a scrambled state as follows: You're given m lists of containing n elements each(representing the ...
Conor James Thomas Warford Hen's user avatar
  • 487
6 votes
2 answers
379 views

A store is having a big sale. If your price reaches $199 or more, you can reduce it by $100. You can buy each product only once. Here's an example list of products: (in order to simplify, the names of ...
Saber's user avatar
  • 173
3 votes
0 answers
130 views

Pretty simple challenge here. Who can make the fastest algorithm (lowest time complexity) to determine whether or not the circle is "boxed in" given the following setup? Input: Your program receives ...
sam-pyt's user avatar
  • 131
4 votes
1 answer
499 views

Introduction Large meetings waste working time. Our aim is to split a large meeting into a number of smaller meetings, so the average number topics that a person discusses is minimized but every ...
Konrad Höffner's user avatar
  • 117
-3 votes
2 answers
1k views

The task is simple: Create an if-statement from scratch in x86 assembly that runs in as few clock-cycles as possible. Must be x86 assembly. Can't use any of the conditional jump/branch instructions (e....
Lance Pollard's user avatar
  • 245
2 votes
1 answer
719 views

The one dimensional twitter waterflow problem is this: You are given an array that represents a hill in the sense that the ith entry is the height of the ith location of the hill. When it rains, ...
Agnishom Chattopadhyay's user avatar
  • 375
1 vote
0 answers
232 views

Introduction I recently came across an oral exam where the candidates were asked to find a logical circuit than can negate 3 inputs A,B,C using only two NOT gates. ...
John Do's user avatar
  • 111
5 votes
1 answer
419 views

Problem Description Given: a function \$f(a, b, c, d, e) = \frac{a \times b}c + \frac de\$ an array \$x = [x_1, x_2, x_3, x_4, ..., x_n]\$ of non-distinct integers a target value \$k\$ What is the ...
Jas's user avatar
  • 51
3 votes
3 answers
752 views

Define f(a,b) := a if b=1; a^f(a,b-1) if b>1 (Tetration, where ^ means power) for positive integers ...
l4m2's user avatar
  • 32.4k
-2 votes
1 answer
252 views

See similar question for 2D case: Find the longest uninterrupted arc The challenge here is to find the longest uninterruped great circle arc around a unit hypersphere in N dimensions, with a random ...
F Chopin's user avatar
  • 269
11 votes
5 answers
610 views

The challenge here is to find the longest uninterruped arc around a unit circle with a random amount of points distributed in random positions around it. Here is a diagram to assist my explanation: ...
F Chopin's user avatar
  • 269
-2 votes
3 answers
379 views

The input is an array (or space-separated string, as you wish), zero-indexed, consisting of one strictly increasing array and one strictly decreasing array (in this order, not other vice versa), each ...
nicael's user avatar
  • 4,811
13 votes
3 answers
627 views

This challenge is from an admission test to a closed number cyber security course. Anyway it doesn't have to do with cyber security, it's just to test the students logical and coding skills. Task ...
user avatar
9 votes
3 answers
1k views

We have a floating point number r between 0 and 1, and an integer p. Find the fraction of integers with the smallest ...
peterh's user avatar
  • 357
3 votes
1 answer
1k views

You have given an array from which we need to remove duplicates. Rules: First or immediate duplicates gets removed first. Array contains natural numbers ...
Satish Patel's user avatar
  • 131
6 votes
2 answers
188 views

Overview Given a 2 dimensional array of values with a filled in rectangle, find the position and size of the rectangle. Do it in the fewest array accesses as possible. Requirements The ...
Daffy's user avatar
  • 1,075
13 votes
2 answers
859 views

The problem: Write a function which, given a cycle length n and a number of cycles m, where 'm' is within ...
Alecto's user avatar
  • 1,622

1
2