44 votes

Longest common substring in linear time

Python 2, 646 bytes ...
Mitch Schwartz's user avatar
38 votes

Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one

Python 3, 102 bytes try:l=eval(input());k=1#)]0[*k**l(tnirp except:k=2#2=k:tpecxe print(k**l*[0])#1=k;))(tupni(lave=l:yrt Try it online! This is of O(1^n), ...
Leaky Nun's user avatar
  • 49.6k
32 votes

Give a permutation with no two consecutive integers next to each other

Jelly, 3 2 bytes ḂÞ Sorts the integers in [1, ..., n] by their LSB. Try it online!
Dennis's user avatar
  • 210k
20 votes

Efficient Bytewise FizzBuzz

JavaScript (Node.js), 145 bytes Saved 2 bytes thanks to @user202729 Expects a BigInt. Outputs # instead of \n for readability. <...
Arnauld's user avatar
  • 188k
18 votes

Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one

Perl 5, 82 73 71+1 (for -n flag) = 72 bytes I'm certain I can golf this (a lot) more, but it's bedtime, I've spent enough time debugging as is, and I'm proud of what I have so far anyway. ...
Chris's user avatar
  • 1,949
18 votes
Accepted

Polite Near-Sighted Drunk Bot on a Minefield

Python 2, 65 bytes def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r) Try it online! The probability the bot is dead can be expressed as: $...
xnor's user avatar
  • 144k
17 votes

Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one

Actually, 20 bytes ";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;" Try it online! Input: 5 Output: rⁿ@╜╖1(; [0] 5 ...
Leaky Nun's user avatar
  • 49.6k
16 votes

Give a permutation with no two consecutive integers next to each other

Python 2, 32 bytes lambda n:(range(n|1)*2)[1:n*2:2] Try it online!
ovs's user avatar
  • 58k
14 votes

Write an Incident tokeniser

C (gcc), 324 bytes The function f takes a null-terminated string and prints the tokens to stdout. All newlines can be removed from the code below. ...
feersum's user avatar
  • 31.3k
13 votes

Sum of set bits from 1 to n

K (ngn/k), 45 32 bytes {+/b*1+(q!'x)+-2!q*<q:2/=#b:2\x} Try it online! Golfing ideas thanks to @ngn and @coltim The OEIS page contains a curious PARI program: <...
Bubbler's user avatar
  • 73.8k
13 votes

Sum of set bits from 1 to n

JavaScript (ES6),  57 54 53  52 bytes n=>(i=0,g=b=>b--&&(n>>b&1&&b+i+i++<<b)+g(b))(32)/2+i Try it online! This is designed ...
Arnauld's user avatar
  • 188k
11 votes

Three, Three, No

JavaScript (V8), 189 164 bytes ...
Unmitigated's user avatar
  • 2,749
10 votes

How many dominoes can you fit here?

Python 3.8 (pre-release), 544 bytes ...
Lynn's user avatar
  • 68.1k
10 votes

Sums of sum of divisors in sublinear time

Ruby, 55 52 bytes Formula is adapted from this math.SE question. Runs in \$\mathcal{O}(\sqrt{n})\$. -3 bytes thanks to @dingledooper. ...
ovs's user avatar
  • 58k
9 votes

Binning in time

R, 48 bytes function(n,s)table(cut(n,0:ceiling(max(n)/s)*s)) Try it online! Once again, table and ...
Giuseppe's user avatar
  • 28.1k
9 votes

Project Euler 1: Multiples in constant time

Jelly, 20 bytes +Ø.÷€AĊc2ḋIɓN;æl¥ƒ-Ḋ Try it online! Port of my own APL answer. Trailing ɓ chain trick is indeed strong :P How ...
Bubbler's user avatar
  • 73.8k
9 votes

Next Special String

Python, 91 bytes (@tsh) f=lambda s,j=0:f(max(s,f"{int(s[:j]+s[:-j]or s,2)+1:0{len(s)}b}"),j+1)if s[j:]else(s<"1")*s Attempt This Online! Previous Python, 98 bytes f=lambda s,j=0:...
loopy walt's user avatar
9 votes

Maximum of outer product of integer vectors (in linear time)

JavaScript (Node.js), 84 bytes f=([a,...x],m=1,n=1)=>a?f(x,Math.min(...q=a.flatMap(c=>[c*m,c*n])),Math.max(...q)):n Try it online! Keep trace of min and max
l4m2's user avatar
  • 20.3k
9 votes

Generate a permutation from the high-water marks

Nibbles, 5 bytes .,@?:-,_@@ Attempt This Online! Puts the \$k\$ highest numbers at the specified indices in ascending order and the remaining numbers at the ...
xigoi's user avatar
  • 7,161
9 votes

Sums of sum of divisors in sublinear time

Python 2, 58 bytes Runs in \$ \mathcal{O}(\sqrt{n}) \$ time. f=lambda n,i=1:~i*i*(n/-~i-n/i)/2+(i<n and f(n,n/(n/-~i))) Try it online! Explanation Note: @Neil'...
dingledooper's user avatar
  • 22.3k
8 votes
Accepted

A classic sorting code-golf question

Haskell, 87 80 89 s%[]=s (x:a)%q|x<=q!!0=x:a%q p%q=q%p j(x:y:s)=x%y:j s j a=a r[x]=x r s=r$j s s=r.map(:[]) This is merge sort, implemented from the bottom up. ...
proud haskeller's user avatar
8 votes

Circular Limited Sums

Python with numpy, 59 bytes lambda M,N:trace(mat(tri(M+1)[::-1])**N) from numpy import* Try it online! Uses matrix multiplication to count paths. If float ...
xnor's user avatar
  • 144k
8 votes

Give a permutation with no two consecutive integers next to each other

Python 3, 40, 38 bytes lambda n:[*range(1,n,2),*range(0,n,2)] Try it online! This runs in O(n) time. Thanks to Dennis for ...
DJMcMayhem's user avatar
  • 58.9k
8 votes

Efficient Bytewise FizzBuzz

Python 2, 216 212 209 189 183 182 bytes ...
Neil's user avatar
  • 165k
8 votes

Project Euler 1: Multiples in constant time

APL (Dyalog Extended), 31 bytes -/+/(⎕+⍳2)(⊢×2!⌈⍤|⍤÷)\∊(⊢,∧)\-⎕ Try it online! Full program which takes the list of divisors, and then the ...
Bubbler's user avatar
  • 73.8k
8 votes

An Scalable Event Scheduler That Can Handle Billions of Events

Proof that this challenge is impossible without extra assumptions I'm assuming here that we can't take advantage of the fact that the range of a Time is limited, ...
8 votes

Compute cumulative means efficiently

APL(Dyalog Unicode), 19 20 bytes SBCS Added 1 byte to fix handling of trailing integers. (⌈¯2-/⌊,⊢/)⊢⍤/+\÷⍳⍤≢ Try it on APLgolf! ...
ovs's user avatar
  • 58k
7 votes
Accepted

Maximise the squared difference

Jelly, 24 21 15 14 10 9 bytes RUĖµ«/€ị" To compute the total squared difference, append µ_ṙ1$²S to the code. Try it online! ...
Dennis's user avatar
  • 210k
7 votes
Accepted

Symmetric boolean functions as Zhegalkin polynomials

Dyalog APL, 15 bytes {2|⍺⌹⍉∘.!⍨0,⍳⍵} Matrix division, basically. Takes input like 0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4 for T4({2,3,4}). <...
lirtosiast's user avatar
  • 21.4k

Only top scored, non community-wiki answers of a minimum length are eligible