# 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

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. ....

7

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): ...

7

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 <...

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

Haskell, 42 bytes f[]=[] f a=f(zipWith(-)a$tail a)++[last a] Try it online! 7 Haskell, 22 bytes foldl(flip$scanr(-))[] Try it online!

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, ...

5

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 ...

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

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

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

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

Python Here's my solution. I think it might still be O(n2), but I think the average case is much better than that. Basically it works by normalizing each string so that any rotation will have the same form. For example: 'amazing' -> 'mazinga' 'mazinga' -> 'mazinga' 'azingam' -> 'mazinga' 'zingama' -> 'mazinga' 'ingamaz' -> 'mazinga' '...

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

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

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 ...

3

Python (3) again The method I used was to calculate a rolling hash of each word starting at each character in the string; since it's a rolling hash, it takes O(n) (where n is the word length) time to compute all the n hashes. The string is treated as a base-1114112 number, which ensures the hashes are unique. (This is similar to the Haskell solution, but ...

3

One way in Ruby To keep within the rules outlined above, I would use a similar strategy as the JavaScript solution and use a hash as an intermediary. merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] ||= el } }.keys Essentially, these are the steps I'm going through in the line above. Define a variable merged_arr that will contain the ...

3

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))

3

O(K log N), many characters of Python Edit: Improved by replacing merge sort with radix sort. This is an improvement over my previous answer, but I'm posting it separately because it's a different strategy, and so the post doesn't get super-long. This is now optimal because simply reading the input can take 2*K*lg N time in the worst case -- 2*K numbers ...

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