# Tag Info

17

JavaScript (ES6),  62 58 49  46 bytes Saved 3 bytes thanks to @Oliver Returns the list as a comma-separated string. f=a=>+a||f(a.map(n=>a-(a=n),a=a.shift()))+[,a] Try it online! Commented f = a => // f = recursive function taking the input list a[] +a // if a[] consists of a single positive integer: ...

10

JavaScript O(N) 131 124 116 92 (86?) Golfed version: function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n} Human readable golfed version: function m(i,x) { h = {} n = [] for (a = 2; a--; i=x) i.map(function(b){ h[b] = h[b] || n.push(b) }) return n } I could use concat like so and do ...

9

Python O(1): Since the challenge has been specified to be using Big O. I concluded that the best way to do it(since the upper bound is limited by a constant) is to just to create a giant look-up array. However, this program would be too big to post here, so I made a program that generates it: def zeroesUpToN(n): zeros = 0 for i in range(n): ...

8

Some thoughts up front: f[i]: number of zeros in [10^i, 2*10^i) g[i]: number of zeros in [10*10^i, 11*10^i) h[i]: number of zeros in [0, 10^i) i f g h 1 1* 10* * 2 1** 10** ** 3 1*** 10*** *** 4 1**** 10**** **** f[i] = 9*f[i - 1] + g[i - 1] g[i] = f[i] + 10^i h[i] = h[i - 1] + 9*f[i - 1] Now the code: def zeros(n): ...

8

Perl27 Characters Simple Perl Hack my @vals = (); push @vals, @arr1, @arr2; my %out; map { $out{$_}++ } @vals; my @unique = keys %out; I'm sure someone could one-liner this.. and thus (Thanks Dom Hastings) sub x{$_{$_}++for@_;keys%_}

8

7 cycles, constant time Here's a solution based on my answer to this SO Question. It uses BSR to count how many bits are needed to hold the number. It looks up how many decimal digits needed to represent the largest number that many bits can hold. Then it subtracts 1 if the actual number is less than the nearest power of 10 with that many digits. ....

8

Haskell, 22 bytes foldl(flip$scanr(-))[] Try it online! 7 JavaScript, O(10p) & 72 bytes r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]} It is trivial to prove that the loop will be done after at most O(10p) iterations. f= r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]} <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow&... 7 Python 3, O(n*log(n)), 167 bytes import math def f(p):p=[math.atan2(*x)for x in p];q=sorted(p);d=[b-a for a,b in zip(q,q[1:])]+[math.pi*2-q[-1]+q[0]];i=d.index(max(d));return map(p.index,(q*2)[i:i+2]) Try it online! The sorting step takes O(n*log(n)) time, all other steps take linear time. Ungolfed import math def f(p): p=[math.atan2(x, y)for x, y in ... 7 Haskell, 42 bytes f[]=[] f a=f(zipWith(-)a$tail a)++[last a] Try it online!

6

C++11 Excuse the variable names. Calculates hamming distance between each pair of words then tries replacing characters in words with '-', and calculates hamming distance between the word with '-' and the words without (that had a low enough hamming distance). See comments for details. #include <algorithm> #include <cassert> #include <...

6

Best case 8 cycles, Worst case 12 cycles Since it is not clear in the question, I am basing this off the Ivy Bridge latencies. The approach here is to use the bsr (bit scan reverse) instruction as a poor-man's log2(). The result is used as an index into a jump table which contains entries for bits 0 to 42. I am assuming that given that operation on 64bit ...

6

TI-BASIC, 54 bytes Ans→L₁:dim(L₁→dim(L₂:While 1-Ans:L₁(Ans→L₂(Ans:-ΔList(L₁→L₁:dim(Ans:End:L₁(Ans→L₂(Ans:L₂ Input is the list of the right side of the triangle in Ans, as is described in the challenge. Output is the top row of said triangle. Examples: {5,2,1 {5 2 1} prgmCDGF19 {2 1 1} {84,42,21,10,2 {84 42 21 10 2} prgmCDGF19 {4 7 ...

6

APL (Dyalog Unicode), O(1) ⊃∘'111111111110… …...

5

C, O(n), 65 95 102 bytes After I made at least one additional test case, some more code naturally needed to be added. Thanks to Serge Mosin for finding another bug. k(int*m){int*i=m;for(;2[i]>*i++;);for(*i-=i[~1]*(1[i]+(i-m>2)*i[~2]>=i[-1]);2[i]<*i++;);return 1+i-m;} Test cases: int a[] = {1, 3, 2, 5, 4, 4, 6, 3, 2}; // -> 6 int b[] = {4, 4, ...

5

Haskell, $O(n \log n)$ time, $O(n)$ space {-# LANGUAGE MultiParamTypeClasses #-} import qualified Data.FingerTree as F data S = S { sSum :: Int , sArr :: [Int] } deriving (Show) instance Monoid S where mempty = S 0 [] mappend _ s = s instance F.Measured S S where measure = id bestSubarrays :: [Int] -> F.FingerTree S S bestSubarrays []...

5

JavaScript (Node.js), O(n), 234 229 228 211 bytes a=>(b=a.map(s=>Math.atan2(...s)/Math.PI+2),k=[],b.map(t=>d=![k[u=t*a.length|1]=t<k[u]?k[u]:t,k[--u]=t>k[u]?k[u]:t]),k.filter(t=>t).map((v,i,s)=>d=d<(t=s[i+1]||s[0]+2)-v?(T=t)-(V=v):d),[T,V].map(x=>b.indexOf(x))) Try it online! Assuming: atan2 is O(1) x.map, x.filter are O(n) ...

5

Area-based algorithm, $O(k^2+n\log(k))$ Our general strategy is to instead select points (outside the sticker rectangles) from the square (-1,-1) to (1,1), then repeat if we don't get a point within the circle. On average, we will have to select $\frac{4}{\pi}$ points from the square for each point in the circle. The runtime is not depend on rectangle ...

4

Java: public class ZeroCount { static final int max = 65498; public static void main(String[] args) { int res = 0; for (int i = 10; i <= max; i*=10) { res += max/i + max/(10*i) * (i-1); res -= (max % (10*i) < i) ? (i-1) - (max % i) / (i/10) : 0; } System.out.println(res); } } Should ...

4

C99, 94, O(n) Edit: everyone seems to refer to struct Node just as Node as if the typedefed it, so I did too. this is actually my first C golf. lots of segfaults. anyways, this requires C99 because it uses a declaration inside a for loop's first statement. void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,...

4

PHP, 69/42 68/41 chars Including the function declaration is 68 characters: function m($a,$b){return array_keys(array_flip($a)+array_flip($b));} Not including the function declaration is 41 characters: array_keys(array_flip($a)+array_flip($b))

4

Python 2.7, 38 chars F=lambda x,y:{c:1 for c in x+y}.keys() Should be O(N) assuming a good hash function. Wasi's 8 character set implementation is better, if you don't think it violates the rules.

4

Reduction to Traveling Salesman Problem, O(n^2*2^n). In the above, n is the number of vertices in the graph. I will give a description of the algorithm for now. Starting with the input graph, carry out the following steps: Create a new graph with edge weights equal to the negation of the input edge weights. These weights represent the value to the taxi ...

4

C++, Where l is the word length, m is the number of "wildcards" (or dashes) and n is the number of words (of length l.) Skimming over the submissions, it seems that they're all either inherently quadratic with the number of words or are very liberal with their use of resources, while there is a very straight-forward O(n log n) solution: For every possible ...

4

Python, O(n log n) I didn't golf this, because I'm competing primarily on the fastest code side of things. My solution is the heaviest_subseq function, and a test harness is also included at the bottom. import bisect import blist def heaviest_subseq(in_list): best_subseq = blist.blist([(0, 0)]) for new_elem in in_list: insert_loc = bisect....

4

Haskell, O(10p) in worst case 121 119 bytes g(0,1,1,1) g(a,b,c,d)r p|z<-floor.(*10^p),u<-a+c,v<-b+d=last$g(last$(u,v,c,d):[(a,b,u,v)|r<u/v])r p:[(u,v)|z r==z(u/v)] Try it online! Saved 2 bytes thanks to Laikoni I used the algorithm from https://math.stackexchange.com/questions/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-...

4

And then I realised that we can be faster, and use no additional registers: cmp eax, ebx mov eax, offset false_case mov ebx, offset true_case cmove eax, ebx ;or cmovb, etc. jmp eax

4

MathGolf, 14 11 bytes xÆ‼├│?;∟;]x Try it online! Explanation x reverse int/array/string Æ ∟ do while true without popping using 5 operators ‼ apply next 2 operators to TOS ├ pop from left of list │ get differences of list ? rot3 ; discard TOS (removes rest from ├ command) ...

4

Jelly, 6 bytes ṚIƬZḢṚ A monadic Link accepting a list of integers which yields a list of integers. Try it online! How? Builds the whole triangle then extracts the required elements. ṚIƬZḢṚ - Link: list of integers e.g. [84,42,21,10,2] Ṛ - reverse [2,10,21,42,84] Ƭ - collect & apply until a fixed ...

4

Ruby, $\mathcal{O}(nm)$ I think I got the analysis for this right. Should be $\mathcal{O}(nm)$ because for each of the $n$ characters in the master sequence, it goes through at most $m$ steps to check each character of the subsequence (if they are all the same character). It's also optimized to try to be $\Omega(n+m)$ best case complexity, which ...

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