Codewars: “Twice linear” is running too long

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
3
down vote

favorite
1












I am doing one kata on codewars:




Consider a sequence u where u is defined as follows:



The number u(0) = 1 is the first one in u. For each x in u, then y = 2
* x + 1 and z = 3 * x + 1 must be in u too. There are no other numbers in u. Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]



1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives
15 and 22 and so on...



Task: Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u.



Example: dbl_linear(10) should return 22



Note: Focus attention on efficiency




So far I did this algorithm but it's too slow and it times out. I do not really know how to refactor it. Can anyone help me? Maybe some another concept how to approach to solve it?



function dblLinear(n) 
let arrOfResult = [1];
const set = new Set();
set.add(1);
let nextInvoker = 0;

while (arrOfResult.length <= n)
let y = 2 * arrOfResult[nextInvoker] + 1;
let z = 3 * arrOfResult[nextInvoker] + 1;

set.add(y);
set.add(z);


arrOfResult = Array.from(set).sort((a, b) => a - b);

nextInvoker++;


arrOfResult.forEach(element =>
let y = 2 * element + 1;
let z = 3 * element + 1;

set.add(y);
set.add(z);
);

const result = Array.from(set).sort((a, b) => a - b);

return result[n];







share|improve this question





















  • @ernesto this code does not compile because it's missing a } but anyway, sorting inside the while loop is unnecessary and incredibly slow (not to mention that you're building an Array from a Set, each time): directly insert items in the right position and drop set all together.
    – Adriano Repetti
    Jun 4 at 8:48










  • @AdrianoRepetti i put sorting after (below) while loop and it's even slower :).
    – Ernesto
    Jun 4 at 8:55










  • @ernesto put the missing } to make clear where things start/ends but the point is the you do not need sorting at all. When inserting you already know where to (binary search for the greatest number smaller than the one you want to insert). Also note that the final size of the array is known in advance then you do not need to create/destroy/copy arrays (and you can preallocate array new Array(the_size_you_need). With slightly more complicate code you don't even need to search but even doing it you'll greatly gain in performance compared to now.
    – Adriano Repetti
    Jun 4 at 9:24










  • More optimisations are possible, for example you do not need to deal with anything > n and you can simply continue plus I have the gut feeling that algorithm itself should be rewritten to be even simpler but I'm kind of lazy then...
    – Adriano Repetti
    Jun 4 at 9:28
















up vote
3
down vote

favorite
1












I am doing one kata on codewars:




Consider a sequence u where u is defined as follows:



The number u(0) = 1 is the first one in u. For each x in u, then y = 2
* x + 1 and z = 3 * x + 1 must be in u too. There are no other numbers in u. Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]



1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives
15 and 22 and so on...



Task: Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u.



Example: dbl_linear(10) should return 22



Note: Focus attention on efficiency




So far I did this algorithm but it's too slow and it times out. I do not really know how to refactor it. Can anyone help me? Maybe some another concept how to approach to solve it?



function dblLinear(n) 
let arrOfResult = [1];
const set = new Set();
set.add(1);
let nextInvoker = 0;

while (arrOfResult.length <= n)
let y = 2 * arrOfResult[nextInvoker] + 1;
let z = 3 * arrOfResult[nextInvoker] + 1;

set.add(y);
set.add(z);


arrOfResult = Array.from(set).sort((a, b) => a - b);

nextInvoker++;


arrOfResult.forEach(element =>
let y = 2 * element + 1;
let z = 3 * element + 1;

set.add(y);
set.add(z);
);

const result = Array.from(set).sort((a, b) => a - b);

return result[n];







share|improve this question





















  • @ernesto this code does not compile because it's missing a } but anyway, sorting inside the while loop is unnecessary and incredibly slow (not to mention that you're building an Array from a Set, each time): directly insert items in the right position and drop set all together.
    – Adriano Repetti
    Jun 4 at 8:48










  • @AdrianoRepetti i put sorting after (below) while loop and it's even slower :).
    – Ernesto
    Jun 4 at 8:55










  • @ernesto put the missing } to make clear where things start/ends but the point is the you do not need sorting at all. When inserting you already know where to (binary search for the greatest number smaller than the one you want to insert). Also note that the final size of the array is known in advance then you do not need to create/destroy/copy arrays (and you can preallocate array new Array(the_size_you_need). With slightly more complicate code you don't even need to search but even doing it you'll greatly gain in performance compared to now.
    – Adriano Repetti
    Jun 4 at 9:24










  • More optimisations are possible, for example you do not need to deal with anything > n and you can simply continue plus I have the gut feeling that algorithm itself should be rewritten to be even simpler but I'm kind of lazy then...
    – Adriano Repetti
    Jun 4 at 9:28












up vote
3
down vote

favorite
1









up vote
3
down vote

favorite
1






1





I am doing one kata on codewars:




Consider a sequence u where u is defined as follows:



The number u(0) = 1 is the first one in u. For each x in u, then y = 2
* x + 1 and z = 3 * x + 1 must be in u too. There are no other numbers in u. Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]



1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives
15 and 22 and so on...



Task: Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u.



Example: dbl_linear(10) should return 22



Note: Focus attention on efficiency




So far I did this algorithm but it's too slow and it times out. I do not really know how to refactor it. Can anyone help me? Maybe some another concept how to approach to solve it?



function dblLinear(n) 
let arrOfResult = [1];
const set = new Set();
set.add(1);
let nextInvoker = 0;

while (arrOfResult.length <= n)
let y = 2 * arrOfResult[nextInvoker] + 1;
let z = 3 * arrOfResult[nextInvoker] + 1;

set.add(y);
set.add(z);


arrOfResult = Array.from(set).sort((a, b) => a - b);

nextInvoker++;


arrOfResult.forEach(element =>
let y = 2 * element + 1;
let z = 3 * element + 1;

set.add(y);
set.add(z);
);

const result = Array.from(set).sort((a, b) => a - b);

return result[n];







share|improve this question













I am doing one kata on codewars:




Consider a sequence u where u is defined as follows:



The number u(0) = 1 is the first one in u. For each x in u, then y = 2
* x + 1 and z = 3 * x + 1 must be in u too. There are no other numbers in u. Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]



1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives
15 and 22 and so on...



Task: Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u.



Example: dbl_linear(10) should return 22



Note: Focus attention on efficiency




So far I did this algorithm but it's too slow and it times out. I do not really know how to refactor it. Can anyone help me? Maybe some another concept how to approach to solve it?



function dblLinear(n) 
let arrOfResult = [1];
const set = new Set();
set.add(1);
let nextInvoker = 0;

while (arrOfResult.length <= n)
let y = 2 * arrOfResult[nextInvoker] + 1;
let z = 3 * arrOfResult[nextInvoker] + 1;

set.add(y);
set.add(z);


arrOfResult = Array.from(set).sort((a, b) => a - b);

nextInvoker++;


arrOfResult.forEach(element =>
let y = 2 * element + 1;
let z = 3 * element + 1;

set.add(y);
set.add(z);
);

const result = Array.from(set).sort((a, b) => a - b);

return result[n];









share|improve this question












share|improve this question




share|improve this question








edited Jun 4 at 18:28









chicks

1,3772818




1,3772818









asked Jun 4 at 7:19









Ernesto

212




212











  • @ernesto this code does not compile because it's missing a } but anyway, sorting inside the while loop is unnecessary and incredibly slow (not to mention that you're building an Array from a Set, each time): directly insert items in the right position and drop set all together.
    – Adriano Repetti
    Jun 4 at 8:48










  • @AdrianoRepetti i put sorting after (below) while loop and it's even slower :).
    – Ernesto
    Jun 4 at 8:55










  • @ernesto put the missing } to make clear where things start/ends but the point is the you do not need sorting at all. When inserting you already know where to (binary search for the greatest number smaller than the one you want to insert). Also note that the final size of the array is known in advance then you do not need to create/destroy/copy arrays (and you can preallocate array new Array(the_size_you_need). With slightly more complicate code you don't even need to search but even doing it you'll greatly gain in performance compared to now.
    – Adriano Repetti
    Jun 4 at 9:24










  • More optimisations are possible, for example you do not need to deal with anything > n and you can simply continue plus I have the gut feeling that algorithm itself should be rewritten to be even simpler but I'm kind of lazy then...
    – Adriano Repetti
    Jun 4 at 9:28
















  • @ernesto this code does not compile because it's missing a } but anyway, sorting inside the while loop is unnecessary and incredibly slow (not to mention that you're building an Array from a Set, each time): directly insert items in the right position and drop set all together.
    – Adriano Repetti
    Jun 4 at 8:48










  • @AdrianoRepetti i put sorting after (below) while loop and it's even slower :).
    – Ernesto
    Jun 4 at 8:55










  • @ernesto put the missing } to make clear where things start/ends but the point is the you do not need sorting at all. When inserting you already know where to (binary search for the greatest number smaller than the one you want to insert). Also note that the final size of the array is known in advance then you do not need to create/destroy/copy arrays (and you can preallocate array new Array(the_size_you_need). With slightly more complicate code you don't even need to search but even doing it you'll greatly gain in performance compared to now.
    – Adriano Repetti
    Jun 4 at 9:24










  • More optimisations are possible, for example you do not need to deal with anything > n and you can simply continue plus I have the gut feeling that algorithm itself should be rewritten to be even simpler but I'm kind of lazy then...
    – Adriano Repetti
    Jun 4 at 9:28















@ernesto this code does not compile because it's missing a } but anyway, sorting inside the while loop is unnecessary and incredibly slow (not to mention that you're building an Array from a Set, each time): directly insert items in the right position and drop set all together.
– Adriano Repetti
Jun 4 at 8:48




@ernesto this code does not compile because it's missing a } but anyway, sorting inside the while loop is unnecessary and incredibly slow (not to mention that you're building an Array from a Set, each time): directly insert items in the right position and drop set all together.
– Adriano Repetti
Jun 4 at 8:48












@AdrianoRepetti i put sorting after (below) while loop and it's even slower :).
– Ernesto
Jun 4 at 8:55




@AdrianoRepetti i put sorting after (below) while loop and it's even slower :).
– Ernesto
Jun 4 at 8:55












@ernesto put the missing } to make clear where things start/ends but the point is the you do not need sorting at all. When inserting you already know where to (binary search for the greatest number smaller than the one you want to insert). Also note that the final size of the array is known in advance then you do not need to create/destroy/copy arrays (and you can preallocate array new Array(the_size_you_need). With slightly more complicate code you don't even need to search but even doing it you'll greatly gain in performance compared to now.
– Adriano Repetti
Jun 4 at 9:24




@ernesto put the missing } to make clear where things start/ends but the point is the you do not need sorting at all. When inserting you already know where to (binary search for the greatest number smaller than the one you want to insert). Also note that the final size of the array is known in advance then you do not need to create/destroy/copy arrays (and you can preallocate array new Array(the_size_you_need). With slightly more complicate code you don't even need to search but even doing it you'll greatly gain in performance compared to now.
– Adriano Repetti
Jun 4 at 9:24












More optimisations are possible, for example you do not need to deal with anything > n and you can simply continue plus I have the gut feeling that algorithm itself should be rewritten to be even simpler but I'm kind of lazy then...
– Adriano Repetti
Jun 4 at 9:28




More optimisations are possible, for example you do not need to deal with anything > n and you can simply continue plus I have the gut feeling that algorithm itself should be rewritten to be even simpler but I'm kind of lazy then...
– Adriano Repetti
Jun 4 at 9:28










3 Answers
3






active

oldest

votes

















up vote
8
down vote













As I understand it, the algorithm employed is as follows:




  • set is a set of numbers, all of which are in the sequence


  • arrOfResult is set in order

  • Invariant: the first nextInvoker + 1 elements of arrOfResult are complete: i.e. they form a prefix of the sequence with no gaps

  • We loop, extending set/arrOfResult by two elements each time until we have n elements, so the prefix is of length n/2 (plus or minus a couple: I haven't worked through the exact details)

  • We then form the closure under the two operations $x to 2x+1$ and $x to 3x+1$ and claim that the prefix of that closure contains the first n elements with no gaps.

The claim of that last point seems to me to need a comment showing why it's true.



But more importantly, the way in which the algorithm works seems to repeat a lot of work.




 arrOfResult = Array.from(set).sort((a, b) => a - b);



sorts the same elements as the previous time round the loop, plus two more, with a full $Omega(n lg n)$ sort.



An easy way to get an asymptotic improvement would be to use a suitable priority queue. A standard binary heap would probably be sufficient. It would also simplify the main method: just three variables (the heap, a counter, and the previous element in order to detect duplicates) and a single loop.



In fact, if you really optimise that loop it's not even necessary to fully implement the binary heap.



function dbl_linear(n) 
var prev = 0,
heap = [1];
while (true)
if (heap[0] === prev)
// Standard heap pop: move last element to replace first and downheap
heap[0] = heap.pop();

else
if (n-- === 0) return heap[0];

// We want to pop x and then insert 2x+1 and 3x+1
// Since 3x+1 is guaranteed to be larger than anything in the heap,
// we can optimise its insertion. Then we can combine the pop and the
// other insertion into one assignment and a downheap.
prev = heap[0];
heap.push(3 * prev + 1);
heap[0] = 2 * prev + 1;


// Push heap[0] down until we restore the heap property
downheap(heap);




downheap not included.




The clever way of tackling a problem about a sequence of integers if you're allowed access to the Internet is to use the Online Encyclopedia of Integer Sequences to see what's known about it. Searching for the prefix given in the problem statement gives two results: the desired sequence with and without duplicates. Since you clearly interpret the (IMO ambiguous) problem statement as being without duplicates, look at the notes on the sequence without duplicates:




...

a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions. - Reinhard Zumkeller, Jul 14 2010

...




A007448 is




Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(floor(n/3)) )




I would be happy to leave it there, but since some commentators doubted my observation that this gave a simple and efficient solution, two implementations.



A naïve implementation (ignoring everything from Zumkeller's comment after the semicolon) would be



function dbl_linear(n) 
var cache = 0 : 1,
a = 1,
knuth = function(n)
while (n--) a = knuth(a);
return a;



But taking into account the observations made after the semicolon we can optimise quite heavily. This is slightly less simple (although a binary search is still simpler than a heap), but more efficient, and easily argued to run in $O(n lg n)$ time:



function dbl_linear(n) 
// a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions.
// - Reinhard Zumkeller, Jul 14 2010

// A007448(n+1) = 1 + min(2 * A007448(n/2), 3 * A007448(n/3))

var A002977 = [1],
i,
ai = 1;

function A007448(x)
// Find the smallest element of A002977 which is larger than x by binary chop
// Invariant: A002977[lb] <= x < A002977[ub]
// To ensure the invariant we need a special case
if (x === 0) return 1;

var lb = 0,
ub = A002977.length - 1,
mid;
while (ub - lb > 1)
mid = lb + ((ub - lb) >> 1);
if (A002977[mid] > x) ub = mid;
else lb = mid;

return A002977[ub];


for (i = 1; i <= n; i++)
ai = 1 + Math.min(2 * A007448(Math.floor((ai - 1) / 2)),
3 * A007448(Math.floor((ai - 1) / 3)));
A002977[i] = ai;


return ai;



Performance measured on tio.run using Spidermonkey. Times based on a single run, so take with a pinch of salt. They are at least illustrative.



n | original code | sineemore's code | heap | naïve Knuth | optimised Knuth
100 | 0.034s | 0.038s | 0.028s | 0.026s | 0.029s
10^3 | 0.185s | 0.031s | 0.028s | 0.032s | 0.031s
10^4 | 15.2s | 0.147s | 0.031s | 0.042s | 0.040s
10^5 | timeout | 8.3s | 0.042s | 0.268s | 0.051s
10^6 | timeout | timeout | 0.195s | 4.4s | 0.155s
10^7 | not tested | not tested | 2.4s | segfault | 1.9s





share|improve this answer



















  • 1




    a very efficient and simple algorithm - if you're a methematician :-P
    – t3chb0t
    Jun 4 at 10:35






  • 1




    @t3chb0t, no amphetamines required ;)
    – Peter Taylor
    Jun 4 at 10:37






  • 1




    @t3chb0t There are good programming-challenges that don't rely on math but they are rare. I agree that math focused problems are not very good for learning how to program because most of the time you can solve those without programming anything at all.
    – yuri
    Jun 4 at 10:58






  • 2




    @JackAidley, I'm aiming more to teach how to fish than to give a fish.
    – Peter Taylor
    Jun 4 at 13:48






  • 2




    @JackAidley, of course it's not faster than solving the original problem, because it solves the original problem. But I think it's quite obvious that a closed recurrence is simpler than one which involves testing set membership. In any case, I've added a naïve implementation (which is already much faster than the final code given in the other answer, and considerable simpler) and an optimised implementation (which is faster still, and about equally complicated at sineemore's code).
    – Peter Taylor
    Jun 5 at 15:18

















up vote
6
down vote













This is not a math baked answer, expect nested loops and heavy memory usage, you were warned



Uniqueness



Being rather oldfansined I tend to skip most new JavaScript features like Set and const, etc. To guranty array uniquness I'll use seen = as a lookup object.



Every time we are adding y or z values to array we'll do seen[y] = true and seen[z] = true.



if (!seen[y]) 
seen[y] = true;
// inserting `y` to queue


// inserting `z` to queue
seen[z] = true;


Order



So I bet the sort thing is the root of all evil in this task. Calling sort in a loop drasticly decreases perfomance. So in place of sorting array every time after insert we will try to keep the array order while inserting.



Every z value will always be the highest number, so we'll queue.push(z). To determine the right index for y we'll loop over current queue.



for (var i = 0; i < queue.length; i++) 
if (queue[i] > y) break;

queue.splice(i, 0, y);


The splice call inserts y at given index i. This way the queue stays in order.



But wait, we are always looping from 0. Let's make this a bit more efficient. We can remember the last i value to start from it next time.



for (var i = last; i < queue.length; i++) 
if (queue[i] > y) break;

queue.splice(i, 0, y);
last = i;


(this gave me great perfomance increase)



Memory



Our lookup object seen and array queue may use lots of space.



var x = queue.shift();
delete seen[x];


The shift call removes the first array element and returns it. delete removes object property.
This way our queue and lookup object will contain only unprocessed values.



Example rewrite:






function dblLinear(n) 

var queue = [1];
var length = 0;
var seen = ;
var last = 0;

while (length < n)
var x = queue.shift();
delete seen[x];
var y = 2 * x + 1;
var z = 3 * x + 1;
if (!seen[y])
seen[y] = true;
for (var i = last; i < queue.length; i++)
if (queue[i] > y) break;

queue.splice(i, 0, y);
last = i;

seen[z] = true;
queue.push(z);
last--;
length++;


return queue[0];



// Usage

function testing(a, b)
if (a !== b) console.log(a, '!==', b)
else console.log('passed');


testing(dblLinear(10), 22);
testing(dblLinear(20), 57);
testing(dblLinear(30), 91);
testing(dblLinear(50), 175);
testing(dblLinear(100), 447);





Best run on codewars gave me 7218ms.






share|improve this answer























  • Nice, I find they should include some hints about what might be useful like splice or shift etc. After all this is so that you learn something.
    – t3chb0t
    Jun 4 at 11:56










  • @t3chb0t, I've added links to MDN.
    – sineemore
    Jun 4 at 12:08










  • I didn't mean you to include links but codewars hints about solving the challange, sorry ;-]
    – t3chb0t
    Jun 4 at 12:10


















up vote
2
down vote













We have two functions:

$Y(x) = 2 * x + 1$

$Z(x) = 3 * x + 1$



We need to apply these two functions to every value x in result



I simply kept two running indices of result representing which x in result we have calculated so far for both the $Y$ function and $Z$ function. I called these values yIndex and zIndex.



I then calculate Y(result[yIndex]) and Z(result[zIndex]) which I called yNext and zNext. I then append the smallest value of these two values to our result and then increment the yIndex or zIndex depending on which function gave the smaller value (or both if they are equal). Repeat until you reach desired n.



This gives $O(n)$ time.



+----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
| currentN | yIndex | zIndex | yNext | zNext | result | comment |
+----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
| 0 | 0 | 0 | 1 | 1 | [1] | Base case, yNext = zNext = 1, increment both, append result |
| 1 | 1 | 1 | 3 | 4 | [1,3] | calculate new yNext and zNext, yNext < zNext, increment yIndex only, append yNext |
| 2 | 2 | 1 | 7 | 4 | [1,3,4] | calculate new yNext using result[yIndex of the previous row], zNext < yNext, increment zIndex only, append zNext |
| 3 | 2 | 2 | 7 | 10 | [1,3,4,7] | ... yNext < zNext, increment yIndex |
| 4 | 3 | 2 | 9 | 10 | [1,3,4,7,9] | ... |
+----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+



Here is the algorithm:



const tail = xs => xs[xs.length - 1]

function dblLinear (n)
const results =
const YZ =
yIndex: 0,
zIndex: 0,
get yNext () return (results[YZ.yIndex] ,
get zNext () return (results[YZ.zIndex]


do
results.push(Math.min(YZ.yNext, YZ.zNext))
YZ.yIndex += tail(results) === YZ.yNext
YZ.zIndex += tail(results) === YZ.zNext
while (results.length < n)

return results.pop()



Performance test between this implementation and Peter Taylor's



​​​​​1031926810​​​​​ at ​​​dblLinear(10000000)​​​ ​quokka.js:52:0​

​​​​​1: 1248.006ms​​​​​

​​​​​1031926810​​​​​ at ​​​dbl_linear2(10000000)​​​ ​quokka.js:55:0​

​​​​​2: 27667.439ms​​​​​





share|improve this answer























    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );








     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f195788%2fcodewars-twice-linear-is-running-too-long%23new-answer', 'question_page');

    );

    Post as a guest






























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    8
    down vote













    As I understand it, the algorithm employed is as follows:




    • set is a set of numbers, all of which are in the sequence


    • arrOfResult is set in order

    • Invariant: the first nextInvoker + 1 elements of arrOfResult are complete: i.e. they form a prefix of the sequence with no gaps

    • We loop, extending set/arrOfResult by two elements each time until we have n elements, so the prefix is of length n/2 (plus or minus a couple: I haven't worked through the exact details)

    • We then form the closure under the two operations $x to 2x+1$ and $x to 3x+1$ and claim that the prefix of that closure contains the first n elements with no gaps.

    The claim of that last point seems to me to need a comment showing why it's true.



    But more importantly, the way in which the algorithm works seems to repeat a lot of work.




     arrOfResult = Array.from(set).sort((a, b) => a - b);



    sorts the same elements as the previous time round the loop, plus two more, with a full $Omega(n lg n)$ sort.



    An easy way to get an asymptotic improvement would be to use a suitable priority queue. A standard binary heap would probably be sufficient. It would also simplify the main method: just three variables (the heap, a counter, and the previous element in order to detect duplicates) and a single loop.



    In fact, if you really optimise that loop it's not even necessary to fully implement the binary heap.



    function dbl_linear(n) 
    var prev = 0,
    heap = [1];
    while (true)
    if (heap[0] === prev)
    // Standard heap pop: move last element to replace first and downheap
    heap[0] = heap.pop();

    else
    if (n-- === 0) return heap[0];

    // We want to pop x and then insert 2x+1 and 3x+1
    // Since 3x+1 is guaranteed to be larger than anything in the heap,
    // we can optimise its insertion. Then we can combine the pop and the
    // other insertion into one assignment and a downheap.
    prev = heap[0];
    heap.push(3 * prev + 1);
    heap[0] = 2 * prev + 1;


    // Push heap[0] down until we restore the heap property
    downheap(heap);




    downheap not included.




    The clever way of tackling a problem about a sequence of integers if you're allowed access to the Internet is to use the Online Encyclopedia of Integer Sequences to see what's known about it. Searching for the prefix given in the problem statement gives two results: the desired sequence with and without duplicates. Since you clearly interpret the (IMO ambiguous) problem statement as being without duplicates, look at the notes on the sequence without duplicates:




    ...

    a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions. - Reinhard Zumkeller, Jul 14 2010

    ...




    A007448 is




    Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(floor(n/3)) )




    I would be happy to leave it there, but since some commentators doubted my observation that this gave a simple and efficient solution, two implementations.



    A naïve implementation (ignoring everything from Zumkeller's comment after the semicolon) would be



    function dbl_linear(n) 
    var cache = 0 : 1,
    a = 1,
    knuth = function(n)
    while (n--) a = knuth(a);
    return a;



    But taking into account the observations made after the semicolon we can optimise quite heavily. This is slightly less simple (although a binary search is still simpler than a heap), but more efficient, and easily argued to run in $O(n lg n)$ time:



    function dbl_linear(n) 
    // a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions.
    // - Reinhard Zumkeller, Jul 14 2010

    // A007448(n+1) = 1 + min(2 * A007448(n/2), 3 * A007448(n/3))

    var A002977 = [1],
    i,
    ai = 1;

    function A007448(x)
    // Find the smallest element of A002977 which is larger than x by binary chop
    // Invariant: A002977[lb] <= x < A002977[ub]
    // To ensure the invariant we need a special case
    if (x === 0) return 1;

    var lb = 0,
    ub = A002977.length - 1,
    mid;
    while (ub - lb > 1)
    mid = lb + ((ub - lb) >> 1);
    if (A002977[mid] > x) ub = mid;
    else lb = mid;

    return A002977[ub];


    for (i = 1; i <= n; i++)
    ai = 1 + Math.min(2 * A007448(Math.floor((ai - 1) / 2)),
    3 * A007448(Math.floor((ai - 1) / 3)));
    A002977[i] = ai;


    return ai;



    Performance measured on tio.run using Spidermonkey. Times based on a single run, so take with a pinch of salt. They are at least illustrative.



    n | original code | sineemore's code | heap | naïve Knuth | optimised Knuth
    100 | 0.034s | 0.038s | 0.028s | 0.026s | 0.029s
    10^3 | 0.185s | 0.031s | 0.028s | 0.032s | 0.031s
    10^4 | 15.2s | 0.147s | 0.031s | 0.042s | 0.040s
    10^5 | timeout | 8.3s | 0.042s | 0.268s | 0.051s
    10^6 | timeout | timeout | 0.195s | 4.4s | 0.155s
    10^7 | not tested | not tested | 2.4s | segfault | 1.9s





    share|improve this answer



















    • 1




      a very efficient and simple algorithm - if you're a methematician :-P
      – t3chb0t
      Jun 4 at 10:35






    • 1




      @t3chb0t, no amphetamines required ;)
      – Peter Taylor
      Jun 4 at 10:37






    • 1




      @t3chb0t There are good programming-challenges that don't rely on math but they are rare. I agree that math focused problems are not very good for learning how to program because most of the time you can solve those without programming anything at all.
      – yuri
      Jun 4 at 10:58






    • 2




      @JackAidley, I'm aiming more to teach how to fish than to give a fish.
      – Peter Taylor
      Jun 4 at 13:48






    • 2




      @JackAidley, of course it's not faster than solving the original problem, because it solves the original problem. But I think it's quite obvious that a closed recurrence is simpler than one which involves testing set membership. In any case, I've added a naïve implementation (which is already much faster than the final code given in the other answer, and considerable simpler) and an optimised implementation (which is faster still, and about equally complicated at sineemore's code).
      – Peter Taylor
      Jun 5 at 15:18














    up vote
    8
    down vote













    As I understand it, the algorithm employed is as follows:




    • set is a set of numbers, all of which are in the sequence


    • arrOfResult is set in order

    • Invariant: the first nextInvoker + 1 elements of arrOfResult are complete: i.e. they form a prefix of the sequence with no gaps

    • We loop, extending set/arrOfResult by two elements each time until we have n elements, so the prefix is of length n/2 (plus or minus a couple: I haven't worked through the exact details)

    • We then form the closure under the two operations $x to 2x+1$ and $x to 3x+1$ and claim that the prefix of that closure contains the first n elements with no gaps.

    The claim of that last point seems to me to need a comment showing why it's true.



    But more importantly, the way in which the algorithm works seems to repeat a lot of work.




     arrOfResult = Array.from(set).sort((a, b) => a - b);



    sorts the same elements as the previous time round the loop, plus two more, with a full $Omega(n lg n)$ sort.



    An easy way to get an asymptotic improvement would be to use a suitable priority queue. A standard binary heap would probably be sufficient. It would also simplify the main method: just three variables (the heap, a counter, and the previous element in order to detect duplicates) and a single loop.



    In fact, if you really optimise that loop it's not even necessary to fully implement the binary heap.



    function dbl_linear(n) 
    var prev = 0,
    heap = [1];
    while (true)
    if (heap[0] === prev)
    // Standard heap pop: move last element to replace first and downheap
    heap[0] = heap.pop();

    else
    if (n-- === 0) return heap[0];

    // We want to pop x and then insert 2x+1 and 3x+1
    // Since 3x+1 is guaranteed to be larger than anything in the heap,
    // we can optimise its insertion. Then we can combine the pop and the
    // other insertion into one assignment and a downheap.
    prev = heap[0];
    heap.push(3 * prev + 1);
    heap[0] = 2 * prev + 1;


    // Push heap[0] down until we restore the heap property
    downheap(heap);




    downheap not included.




    The clever way of tackling a problem about a sequence of integers if you're allowed access to the Internet is to use the Online Encyclopedia of Integer Sequences to see what's known about it. Searching for the prefix given in the problem statement gives two results: the desired sequence with and without duplicates. Since you clearly interpret the (IMO ambiguous) problem statement as being without duplicates, look at the notes on the sequence without duplicates:




    ...

    a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions. - Reinhard Zumkeller, Jul 14 2010

    ...




    A007448 is




    Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(floor(n/3)) )




    I would be happy to leave it there, but since some commentators doubted my observation that this gave a simple and efficient solution, two implementations.



    A naïve implementation (ignoring everything from Zumkeller's comment after the semicolon) would be



    function dbl_linear(n) 
    var cache = 0 : 1,
    a = 1,
    knuth = function(n)
    while (n--) a = knuth(a);
    return a;



    But taking into account the observations made after the semicolon we can optimise quite heavily. This is slightly less simple (although a binary search is still simpler than a heap), but more efficient, and easily argued to run in $O(n lg n)$ time:



    function dbl_linear(n) 
    // a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions.
    // - Reinhard Zumkeller, Jul 14 2010

    // A007448(n+1) = 1 + min(2 * A007448(n/2), 3 * A007448(n/3))

    var A002977 = [1],
    i,
    ai = 1;

    function A007448(x)
    // Find the smallest element of A002977 which is larger than x by binary chop
    // Invariant: A002977[lb] <= x < A002977[ub]
    // To ensure the invariant we need a special case
    if (x === 0) return 1;

    var lb = 0,
    ub = A002977.length - 1,
    mid;
    while (ub - lb > 1)
    mid = lb + ((ub - lb) >> 1);
    if (A002977[mid] > x) ub = mid;
    else lb = mid;

    return A002977[ub];


    for (i = 1; i <= n; i++)
    ai = 1 + Math.min(2 * A007448(Math.floor((ai - 1) / 2)),
    3 * A007448(Math.floor((ai - 1) / 3)));
    A002977[i] = ai;


    return ai;



    Performance measured on tio.run using Spidermonkey. Times based on a single run, so take with a pinch of salt. They are at least illustrative.



    n | original code | sineemore's code | heap | naïve Knuth | optimised Knuth
    100 | 0.034s | 0.038s | 0.028s | 0.026s | 0.029s
    10^3 | 0.185s | 0.031s | 0.028s | 0.032s | 0.031s
    10^4 | 15.2s | 0.147s | 0.031s | 0.042s | 0.040s
    10^5 | timeout | 8.3s | 0.042s | 0.268s | 0.051s
    10^6 | timeout | timeout | 0.195s | 4.4s | 0.155s
    10^7 | not tested | not tested | 2.4s | segfault | 1.9s





    share|improve this answer



















    • 1




      a very efficient and simple algorithm - if you're a methematician :-P
      – t3chb0t
      Jun 4 at 10:35






    • 1




      @t3chb0t, no amphetamines required ;)
      – Peter Taylor
      Jun 4 at 10:37






    • 1




      @t3chb0t There are good programming-challenges that don't rely on math but they are rare. I agree that math focused problems are not very good for learning how to program because most of the time you can solve those without programming anything at all.
      – yuri
      Jun 4 at 10:58






    • 2




      @JackAidley, I'm aiming more to teach how to fish than to give a fish.
      – Peter Taylor
      Jun 4 at 13:48






    • 2




      @JackAidley, of course it's not faster than solving the original problem, because it solves the original problem. But I think it's quite obvious that a closed recurrence is simpler than one which involves testing set membership. In any case, I've added a naïve implementation (which is already much faster than the final code given in the other answer, and considerable simpler) and an optimised implementation (which is faster still, and about equally complicated at sineemore's code).
      – Peter Taylor
      Jun 5 at 15:18












    up vote
    8
    down vote










    up vote
    8
    down vote









    As I understand it, the algorithm employed is as follows:




    • set is a set of numbers, all of which are in the sequence


    • arrOfResult is set in order

    • Invariant: the first nextInvoker + 1 elements of arrOfResult are complete: i.e. they form a prefix of the sequence with no gaps

    • We loop, extending set/arrOfResult by two elements each time until we have n elements, so the prefix is of length n/2 (plus or minus a couple: I haven't worked through the exact details)

    • We then form the closure under the two operations $x to 2x+1$ and $x to 3x+1$ and claim that the prefix of that closure contains the first n elements with no gaps.

    The claim of that last point seems to me to need a comment showing why it's true.



    But more importantly, the way in which the algorithm works seems to repeat a lot of work.




     arrOfResult = Array.from(set).sort((a, b) => a - b);



    sorts the same elements as the previous time round the loop, plus two more, with a full $Omega(n lg n)$ sort.



    An easy way to get an asymptotic improvement would be to use a suitable priority queue. A standard binary heap would probably be sufficient. It would also simplify the main method: just three variables (the heap, a counter, and the previous element in order to detect duplicates) and a single loop.



    In fact, if you really optimise that loop it's not even necessary to fully implement the binary heap.



    function dbl_linear(n) 
    var prev = 0,
    heap = [1];
    while (true)
    if (heap[0] === prev)
    // Standard heap pop: move last element to replace first and downheap
    heap[0] = heap.pop();

    else
    if (n-- === 0) return heap[0];

    // We want to pop x and then insert 2x+1 and 3x+1
    // Since 3x+1 is guaranteed to be larger than anything in the heap,
    // we can optimise its insertion. Then we can combine the pop and the
    // other insertion into one assignment and a downheap.
    prev = heap[0];
    heap.push(3 * prev + 1);
    heap[0] = 2 * prev + 1;


    // Push heap[0] down until we restore the heap property
    downheap(heap);




    downheap not included.




    The clever way of tackling a problem about a sequence of integers if you're allowed access to the Internet is to use the Online Encyclopedia of Integer Sequences to see what's known about it. Searching for the prefix given in the problem statement gives two results: the desired sequence with and without duplicates. Since you clearly interpret the (IMO ambiguous) problem statement as being without duplicates, look at the notes on the sequence without duplicates:




    ...

    a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions. - Reinhard Zumkeller, Jul 14 2010

    ...




    A007448 is




    Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(floor(n/3)) )




    I would be happy to leave it there, but since some commentators doubted my observation that this gave a simple and efficient solution, two implementations.



    A naïve implementation (ignoring everything from Zumkeller's comment after the semicolon) would be



    function dbl_linear(n) 
    var cache = 0 : 1,
    a = 1,
    knuth = function(n)
    while (n--) a = knuth(a);
    return a;



    But taking into account the observations made after the semicolon we can optimise quite heavily. This is slightly less simple (although a binary search is still simpler than a heap), but more efficient, and easily argued to run in $O(n lg n)$ time:



    function dbl_linear(n) 
    // a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions.
    // - Reinhard Zumkeller, Jul 14 2010

    // A007448(n+1) = 1 + min(2 * A007448(n/2), 3 * A007448(n/3))

    var A002977 = [1],
    i,
    ai = 1;

    function A007448(x)
    // Find the smallest element of A002977 which is larger than x by binary chop
    // Invariant: A002977[lb] <= x < A002977[ub]
    // To ensure the invariant we need a special case
    if (x === 0) return 1;

    var lb = 0,
    ub = A002977.length - 1,
    mid;
    while (ub - lb > 1)
    mid = lb + ((ub - lb) >> 1);
    if (A002977[mid] > x) ub = mid;
    else lb = mid;

    return A002977[ub];


    for (i = 1; i <= n; i++)
    ai = 1 + Math.min(2 * A007448(Math.floor((ai - 1) / 2)),
    3 * A007448(Math.floor((ai - 1) / 3)));
    A002977[i] = ai;


    return ai;



    Performance measured on tio.run using Spidermonkey. Times based on a single run, so take with a pinch of salt. They are at least illustrative.



    n | original code | sineemore's code | heap | naïve Knuth | optimised Knuth
    100 | 0.034s | 0.038s | 0.028s | 0.026s | 0.029s
    10^3 | 0.185s | 0.031s | 0.028s | 0.032s | 0.031s
    10^4 | 15.2s | 0.147s | 0.031s | 0.042s | 0.040s
    10^5 | timeout | 8.3s | 0.042s | 0.268s | 0.051s
    10^6 | timeout | timeout | 0.195s | 4.4s | 0.155s
    10^7 | not tested | not tested | 2.4s | segfault | 1.9s





    share|improve this answer















    As I understand it, the algorithm employed is as follows:




    • set is a set of numbers, all of which are in the sequence


    • arrOfResult is set in order

    • Invariant: the first nextInvoker + 1 elements of arrOfResult are complete: i.e. they form a prefix of the sequence with no gaps

    • We loop, extending set/arrOfResult by two elements each time until we have n elements, so the prefix is of length n/2 (plus or minus a couple: I haven't worked through the exact details)

    • We then form the closure under the two operations $x to 2x+1$ and $x to 3x+1$ and claim that the prefix of that closure contains the first n elements with no gaps.

    The claim of that last point seems to me to need a comment showing why it's true.



    But more importantly, the way in which the algorithm works seems to repeat a lot of work.




     arrOfResult = Array.from(set).sort((a, b) => a - b);



    sorts the same elements as the previous time round the loop, plus two more, with a full $Omega(n lg n)$ sort.



    An easy way to get an asymptotic improvement would be to use a suitable priority queue. A standard binary heap would probably be sufficient. It would also simplify the main method: just three variables (the heap, a counter, and the previous element in order to detect duplicates) and a single loop.



    In fact, if you really optimise that loop it's not even necessary to fully implement the binary heap.



    function dbl_linear(n) 
    var prev = 0,
    heap = [1];
    while (true)
    if (heap[0] === prev)
    // Standard heap pop: move last element to replace first and downheap
    heap[0] = heap.pop();

    else
    if (n-- === 0) return heap[0];

    // We want to pop x and then insert 2x+1 and 3x+1
    // Since 3x+1 is guaranteed to be larger than anything in the heap,
    // we can optimise its insertion. Then we can combine the pop and the
    // other insertion into one assignment and a downheap.
    prev = heap[0];
    heap.push(3 * prev + 1);
    heap[0] = 2 * prev + 1;


    // Push heap[0] down until we restore the heap property
    downheap(heap);




    downheap not included.




    The clever way of tackling a problem about a sequence of integers if you're allowed access to the Internet is to use the Online Encyclopedia of Integer Sequences to see what's known about it. Searching for the prefix given in the problem statement gives two results: the desired sequence with and without duplicates. Since you clearly interpret the (IMO ambiguous) problem statement as being without duplicates, look at the notes on the sequence without duplicates:




    ...

    a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions. - Reinhard Zumkeller, Jul 14 2010

    ...




    A007448 is




    Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(floor(n/3)) )




    I would be happy to leave it there, but since some commentators doubted my observation that this gave a simple and efficient solution, two implementations.



    A naïve implementation (ignoring everything from Zumkeller's comment after the semicolon) would be



    function dbl_linear(n) 
    var cache = 0 : 1,
    a = 1,
    knuth = function(n)
    while (n--) a = knuth(a);
    return a;



    But taking into account the observations made after the semicolon we can optimise quite heavily. This is slightly less simple (although a binary search is still simpler than a heap), but more efficient, and easily argued to run in $O(n lg n)$ time:



    function dbl_linear(n) 
    // a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions.
    // - Reinhard Zumkeller, Jul 14 2010

    // A007448(n+1) = 1 + min(2 * A007448(n/2), 3 * A007448(n/3))

    var A002977 = [1],
    i,
    ai = 1;

    function A007448(x)
    // Find the smallest element of A002977 which is larger than x by binary chop
    // Invariant: A002977[lb] <= x < A002977[ub]
    // To ensure the invariant we need a special case
    if (x === 0) return 1;

    var lb = 0,
    ub = A002977.length - 1,
    mid;
    while (ub - lb > 1)
    mid = lb + ((ub - lb) >> 1);
    if (A002977[mid] > x) ub = mid;
    else lb = mid;

    return A002977[ub];


    for (i = 1; i <= n; i++)
    ai = 1 + Math.min(2 * A007448(Math.floor((ai - 1) / 2)),
    3 * A007448(Math.floor((ai - 1) / 3)));
    A002977[i] = ai;


    return ai;



    Performance measured on tio.run using Spidermonkey. Times based on a single run, so take with a pinch of salt. They are at least illustrative.



    n | original code | sineemore's code | heap | naïve Knuth | optimised Knuth
    100 | 0.034s | 0.038s | 0.028s | 0.026s | 0.029s
    10^3 | 0.185s | 0.031s | 0.028s | 0.032s | 0.031s
    10^4 | 15.2s | 0.147s | 0.031s | 0.042s | 0.040s
    10^5 | timeout | 8.3s | 0.042s | 0.268s | 0.051s
    10^6 | timeout | timeout | 0.195s | 4.4s | 0.155s
    10^7 | not tested | not tested | 2.4s | segfault | 1.9s






    share|improve this answer















    share|improve this answer



    share|improve this answer








    edited Jun 5 at 21:14


























    answered Jun 4 at 10:31









    Peter Taylor

    14k2454




    14k2454







    • 1




      a very efficient and simple algorithm - if you're a methematician :-P
      – t3chb0t
      Jun 4 at 10:35






    • 1




      @t3chb0t, no amphetamines required ;)
      – Peter Taylor
      Jun 4 at 10:37






    • 1




      @t3chb0t There are good programming-challenges that don't rely on math but they are rare. I agree that math focused problems are not very good for learning how to program because most of the time you can solve those without programming anything at all.
      – yuri
      Jun 4 at 10:58






    • 2




      @JackAidley, I'm aiming more to teach how to fish than to give a fish.
      – Peter Taylor
      Jun 4 at 13:48






    • 2




      @JackAidley, of course it's not faster than solving the original problem, because it solves the original problem. But I think it's quite obvious that a closed recurrence is simpler than one which involves testing set membership. In any case, I've added a naïve implementation (which is already much faster than the final code given in the other answer, and considerable simpler) and an optimised implementation (which is faster still, and about equally complicated at sineemore's code).
      – Peter Taylor
      Jun 5 at 15:18












    • 1




      a very efficient and simple algorithm - if you're a methematician :-P
      – t3chb0t
      Jun 4 at 10:35






    • 1




      @t3chb0t, no amphetamines required ;)
      – Peter Taylor
      Jun 4 at 10:37






    • 1




      @t3chb0t There are good programming-challenges that don't rely on math but they are rare. I agree that math focused problems are not very good for learning how to program because most of the time you can solve those without programming anything at all.
      – yuri
      Jun 4 at 10:58






    • 2




      @JackAidley, I'm aiming more to teach how to fish than to give a fish.
      – Peter Taylor
      Jun 4 at 13:48






    • 2




      @JackAidley, of course it's not faster than solving the original problem, because it solves the original problem. But I think it's quite obvious that a closed recurrence is simpler than one which involves testing set membership. In any case, I've added a naïve implementation (which is already much faster than the final code given in the other answer, and considerable simpler) and an optimised implementation (which is faster still, and about equally complicated at sineemore's code).
      – Peter Taylor
      Jun 5 at 15:18







    1




    1




    a very efficient and simple algorithm - if you're a methematician :-P
    – t3chb0t
    Jun 4 at 10:35




    a very efficient and simple algorithm - if you're a methematician :-P
    – t3chb0t
    Jun 4 at 10:35




    1




    1




    @t3chb0t, no amphetamines required ;)
    – Peter Taylor
    Jun 4 at 10:37




    @t3chb0t, no amphetamines required ;)
    – Peter Taylor
    Jun 4 at 10:37




    1




    1




    @t3chb0t There are good programming-challenges that don't rely on math but they are rare. I agree that math focused problems are not very good for learning how to program because most of the time you can solve those without programming anything at all.
    – yuri
    Jun 4 at 10:58




    @t3chb0t There are good programming-challenges that don't rely on math but they are rare. I agree that math focused problems are not very good for learning how to program because most of the time you can solve those without programming anything at all.
    – yuri
    Jun 4 at 10:58




    2




    2




    @JackAidley, I'm aiming more to teach how to fish than to give a fish.
    – Peter Taylor
    Jun 4 at 13:48




    @JackAidley, I'm aiming more to teach how to fish than to give a fish.
    – Peter Taylor
    Jun 4 at 13:48




    2




    2




    @JackAidley, of course it's not faster than solving the original problem, because it solves the original problem. But I think it's quite obvious that a closed recurrence is simpler than one which involves testing set membership. In any case, I've added a naïve implementation (which is already much faster than the final code given in the other answer, and considerable simpler) and an optimised implementation (which is faster still, and about equally complicated at sineemore's code).
    – Peter Taylor
    Jun 5 at 15:18




    @JackAidley, of course it's not faster than solving the original problem, because it solves the original problem. But I think it's quite obvious that a closed recurrence is simpler than one which involves testing set membership. In any case, I've added a naïve implementation (which is already much faster than the final code given in the other answer, and considerable simpler) and an optimised implementation (which is faster still, and about equally complicated at sineemore's code).
    – Peter Taylor
    Jun 5 at 15:18












    up vote
    6
    down vote













    This is not a math baked answer, expect nested loops and heavy memory usage, you were warned



    Uniqueness



    Being rather oldfansined I tend to skip most new JavaScript features like Set and const, etc. To guranty array uniquness I'll use seen = as a lookup object.



    Every time we are adding y or z values to array we'll do seen[y] = true and seen[z] = true.



    if (!seen[y]) 
    seen[y] = true;
    // inserting `y` to queue


    // inserting `z` to queue
    seen[z] = true;


    Order



    So I bet the sort thing is the root of all evil in this task. Calling sort in a loop drasticly decreases perfomance. So in place of sorting array every time after insert we will try to keep the array order while inserting.



    Every z value will always be the highest number, so we'll queue.push(z). To determine the right index for y we'll loop over current queue.



    for (var i = 0; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);


    The splice call inserts y at given index i. This way the queue stays in order.



    But wait, we are always looping from 0. Let's make this a bit more efficient. We can remember the last i value to start from it next time.



    for (var i = last; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;


    (this gave me great perfomance increase)



    Memory



    Our lookup object seen and array queue may use lots of space.



    var x = queue.shift();
    delete seen[x];


    The shift call removes the first array element and returns it. delete removes object property.
    This way our queue and lookup object will contain only unprocessed values.



    Example rewrite:






    function dblLinear(n) 

    var queue = [1];
    var length = 0;
    var seen = ;
    var last = 0;

    while (length < n)
    var x = queue.shift();
    delete seen[x];
    var y = 2 * x + 1;
    var z = 3 * x + 1;
    if (!seen[y])
    seen[y] = true;
    for (var i = last; i < queue.length; i++)
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;

    seen[z] = true;
    queue.push(z);
    last--;
    length++;


    return queue[0];



    // Usage

    function testing(a, b)
    if (a !== b) console.log(a, '!==', b)
    else console.log('passed');


    testing(dblLinear(10), 22);
    testing(dblLinear(20), 57);
    testing(dblLinear(30), 91);
    testing(dblLinear(50), 175);
    testing(dblLinear(100), 447);





    Best run on codewars gave me 7218ms.






    share|improve this answer























    • Nice, I find they should include some hints about what might be useful like splice or shift etc. After all this is so that you learn something.
      – t3chb0t
      Jun 4 at 11:56










    • @t3chb0t, I've added links to MDN.
      – sineemore
      Jun 4 at 12:08










    • I didn't mean you to include links but codewars hints about solving the challange, sorry ;-]
      – t3chb0t
      Jun 4 at 12:10















    up vote
    6
    down vote













    This is not a math baked answer, expect nested loops and heavy memory usage, you were warned



    Uniqueness



    Being rather oldfansined I tend to skip most new JavaScript features like Set and const, etc. To guranty array uniquness I'll use seen = as a lookup object.



    Every time we are adding y or z values to array we'll do seen[y] = true and seen[z] = true.



    if (!seen[y]) 
    seen[y] = true;
    // inserting `y` to queue


    // inserting `z` to queue
    seen[z] = true;


    Order



    So I bet the sort thing is the root of all evil in this task. Calling sort in a loop drasticly decreases perfomance. So in place of sorting array every time after insert we will try to keep the array order while inserting.



    Every z value will always be the highest number, so we'll queue.push(z). To determine the right index for y we'll loop over current queue.



    for (var i = 0; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);


    The splice call inserts y at given index i. This way the queue stays in order.



    But wait, we are always looping from 0. Let's make this a bit more efficient. We can remember the last i value to start from it next time.



    for (var i = last; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;


    (this gave me great perfomance increase)



    Memory



    Our lookup object seen and array queue may use lots of space.



    var x = queue.shift();
    delete seen[x];


    The shift call removes the first array element and returns it. delete removes object property.
    This way our queue and lookup object will contain only unprocessed values.



    Example rewrite:






    function dblLinear(n) 

    var queue = [1];
    var length = 0;
    var seen = ;
    var last = 0;

    while (length < n)
    var x = queue.shift();
    delete seen[x];
    var y = 2 * x + 1;
    var z = 3 * x + 1;
    if (!seen[y])
    seen[y] = true;
    for (var i = last; i < queue.length; i++)
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;

    seen[z] = true;
    queue.push(z);
    last--;
    length++;


    return queue[0];



    // Usage

    function testing(a, b)
    if (a !== b) console.log(a, '!==', b)
    else console.log('passed');


    testing(dblLinear(10), 22);
    testing(dblLinear(20), 57);
    testing(dblLinear(30), 91);
    testing(dblLinear(50), 175);
    testing(dblLinear(100), 447);





    Best run on codewars gave me 7218ms.






    share|improve this answer























    • Nice, I find they should include some hints about what might be useful like splice or shift etc. After all this is so that you learn something.
      – t3chb0t
      Jun 4 at 11:56










    • @t3chb0t, I've added links to MDN.
      – sineemore
      Jun 4 at 12:08










    • I didn't mean you to include links but codewars hints about solving the challange, sorry ;-]
      – t3chb0t
      Jun 4 at 12:10













    up vote
    6
    down vote










    up vote
    6
    down vote









    This is not a math baked answer, expect nested loops and heavy memory usage, you were warned



    Uniqueness



    Being rather oldfansined I tend to skip most new JavaScript features like Set and const, etc. To guranty array uniquness I'll use seen = as a lookup object.



    Every time we are adding y or z values to array we'll do seen[y] = true and seen[z] = true.



    if (!seen[y]) 
    seen[y] = true;
    // inserting `y` to queue


    // inserting `z` to queue
    seen[z] = true;


    Order



    So I bet the sort thing is the root of all evil in this task. Calling sort in a loop drasticly decreases perfomance. So in place of sorting array every time after insert we will try to keep the array order while inserting.



    Every z value will always be the highest number, so we'll queue.push(z). To determine the right index for y we'll loop over current queue.



    for (var i = 0; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);


    The splice call inserts y at given index i. This way the queue stays in order.



    But wait, we are always looping from 0. Let's make this a bit more efficient. We can remember the last i value to start from it next time.



    for (var i = last; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;


    (this gave me great perfomance increase)



    Memory



    Our lookup object seen and array queue may use lots of space.



    var x = queue.shift();
    delete seen[x];


    The shift call removes the first array element and returns it. delete removes object property.
    This way our queue and lookup object will contain only unprocessed values.



    Example rewrite:






    function dblLinear(n) 

    var queue = [1];
    var length = 0;
    var seen = ;
    var last = 0;

    while (length < n)
    var x = queue.shift();
    delete seen[x];
    var y = 2 * x + 1;
    var z = 3 * x + 1;
    if (!seen[y])
    seen[y] = true;
    for (var i = last; i < queue.length; i++)
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;

    seen[z] = true;
    queue.push(z);
    last--;
    length++;


    return queue[0];



    // Usage

    function testing(a, b)
    if (a !== b) console.log(a, '!==', b)
    else console.log('passed');


    testing(dblLinear(10), 22);
    testing(dblLinear(20), 57);
    testing(dblLinear(30), 91);
    testing(dblLinear(50), 175);
    testing(dblLinear(100), 447);





    Best run on codewars gave me 7218ms.






    share|improve this answer















    This is not a math baked answer, expect nested loops and heavy memory usage, you were warned



    Uniqueness



    Being rather oldfansined I tend to skip most new JavaScript features like Set and const, etc. To guranty array uniquness I'll use seen = as a lookup object.



    Every time we are adding y or z values to array we'll do seen[y] = true and seen[z] = true.



    if (!seen[y]) 
    seen[y] = true;
    // inserting `y` to queue


    // inserting `z` to queue
    seen[z] = true;


    Order



    So I bet the sort thing is the root of all evil in this task. Calling sort in a loop drasticly decreases perfomance. So in place of sorting array every time after insert we will try to keep the array order while inserting.



    Every z value will always be the highest number, so we'll queue.push(z). To determine the right index for y we'll loop over current queue.



    for (var i = 0; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);


    The splice call inserts y at given index i. This way the queue stays in order.



    But wait, we are always looping from 0. Let's make this a bit more efficient. We can remember the last i value to start from it next time.



    for (var i = last; i < queue.length; i++) 
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;


    (this gave me great perfomance increase)



    Memory



    Our lookup object seen and array queue may use lots of space.



    var x = queue.shift();
    delete seen[x];


    The shift call removes the first array element and returns it. delete removes object property.
    This way our queue and lookup object will contain only unprocessed values.



    Example rewrite:






    function dblLinear(n) 

    var queue = [1];
    var length = 0;
    var seen = ;
    var last = 0;

    while (length < n)
    var x = queue.shift();
    delete seen[x];
    var y = 2 * x + 1;
    var z = 3 * x + 1;
    if (!seen[y])
    seen[y] = true;
    for (var i = last; i < queue.length; i++)
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;

    seen[z] = true;
    queue.push(z);
    last--;
    length++;


    return queue[0];



    // Usage

    function testing(a, b)
    if (a !== b) console.log(a, '!==', b)
    else console.log('passed');


    testing(dblLinear(10), 22);
    testing(dblLinear(20), 57);
    testing(dblLinear(30), 91);
    testing(dblLinear(50), 175);
    testing(dblLinear(100), 447);





    Best run on codewars gave me 7218ms.






    function dblLinear(n) 

    var queue = [1];
    var length = 0;
    var seen = ;
    var last = 0;

    while (length < n)
    var x = queue.shift();
    delete seen[x];
    var y = 2 * x + 1;
    var z = 3 * x + 1;
    if (!seen[y])
    seen[y] = true;
    for (var i = last; i < queue.length; i++)
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;

    seen[z] = true;
    queue.push(z);
    last--;
    length++;


    return queue[0];



    // Usage

    function testing(a, b)
    if (a !== b) console.log(a, '!==', b)
    else console.log('passed');


    testing(dblLinear(10), 22);
    testing(dblLinear(20), 57);
    testing(dblLinear(30), 91);
    testing(dblLinear(50), 175);
    testing(dblLinear(100), 447);





    function dblLinear(n) 

    var queue = [1];
    var length = 0;
    var seen = ;
    var last = 0;

    while (length < n)
    var x = queue.shift();
    delete seen[x];
    var y = 2 * x + 1;
    var z = 3 * x + 1;
    if (!seen[y])
    seen[y] = true;
    for (var i = last; i < queue.length; i++)
    if (queue[i] > y) break;

    queue.splice(i, 0, y);
    last = i;

    seen[z] = true;
    queue.push(z);
    last--;
    length++;


    return queue[0];



    // Usage

    function testing(a, b)
    if (a !== b) console.log(a, '!==', b)
    else console.log('passed');


    testing(dblLinear(10), 22);
    testing(dblLinear(20), 57);
    testing(dblLinear(30), 91);
    testing(dblLinear(50), 175);
    testing(dblLinear(100), 447);






    share|improve this answer















    share|improve this answer



    share|improve this answer








    edited Jun 4 at 12:51


























    answered Jun 4 at 11:50









    sineemore

    1,173217




    1,173217











    • Nice, I find they should include some hints about what might be useful like splice or shift etc. After all this is so that you learn something.
      – t3chb0t
      Jun 4 at 11:56










    • @t3chb0t, I've added links to MDN.
      – sineemore
      Jun 4 at 12:08










    • I didn't mean you to include links but codewars hints about solving the challange, sorry ;-]
      – t3chb0t
      Jun 4 at 12:10

















    • Nice, I find they should include some hints about what might be useful like splice or shift etc. After all this is so that you learn something.
      – t3chb0t
      Jun 4 at 11:56










    • @t3chb0t, I've added links to MDN.
      – sineemore
      Jun 4 at 12:08










    • I didn't mean you to include links but codewars hints about solving the challange, sorry ;-]
      – t3chb0t
      Jun 4 at 12:10
















    Nice, I find they should include some hints about what might be useful like splice or shift etc. After all this is so that you learn something.
    – t3chb0t
    Jun 4 at 11:56




    Nice, I find they should include some hints about what might be useful like splice or shift etc. After all this is so that you learn something.
    – t3chb0t
    Jun 4 at 11:56












    @t3chb0t, I've added links to MDN.
    – sineemore
    Jun 4 at 12:08




    @t3chb0t, I've added links to MDN.
    – sineemore
    Jun 4 at 12:08












    I didn't mean you to include links but codewars hints about solving the challange, sorry ;-]
    – t3chb0t
    Jun 4 at 12:10





    I didn't mean you to include links but codewars hints about solving the challange, sorry ;-]
    – t3chb0t
    Jun 4 at 12:10











    up vote
    2
    down vote













    We have two functions:

    $Y(x) = 2 * x + 1$

    $Z(x) = 3 * x + 1$



    We need to apply these two functions to every value x in result



    I simply kept two running indices of result representing which x in result we have calculated so far for both the $Y$ function and $Z$ function. I called these values yIndex and zIndex.



    I then calculate Y(result[yIndex]) and Z(result[zIndex]) which I called yNext and zNext. I then append the smallest value of these two values to our result and then increment the yIndex or zIndex depending on which function gave the smaller value (or both if they are equal). Repeat until you reach desired n.



    This gives $O(n)$ time.



    +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
    | currentN | yIndex | zIndex | yNext | zNext | result | comment |
    +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
    | 0 | 0 | 0 | 1 | 1 | [1] | Base case, yNext = zNext = 1, increment both, append result |
    | 1 | 1 | 1 | 3 | 4 | [1,3] | calculate new yNext and zNext, yNext < zNext, increment yIndex only, append yNext |
    | 2 | 2 | 1 | 7 | 4 | [1,3,4] | calculate new yNext using result[yIndex of the previous row], zNext < yNext, increment zIndex only, append zNext |
    | 3 | 2 | 2 | 7 | 10 | [1,3,4,7] | ... yNext < zNext, increment yIndex |
    | 4 | 3 | 2 | 9 | 10 | [1,3,4,7,9] | ... |
    +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+



    Here is the algorithm:



    const tail = xs => xs[xs.length - 1]

    function dblLinear (n)
    const results =
    const YZ =
    yIndex: 0,
    zIndex: 0,
    get yNext () return (results[YZ.yIndex] ,
    get zNext () return (results[YZ.zIndex]


    do
    results.push(Math.min(YZ.yNext, YZ.zNext))
    YZ.yIndex += tail(results) === YZ.yNext
    YZ.zIndex += tail(results) === YZ.zNext
    while (results.length < n)

    return results.pop()



    Performance test between this implementation and Peter Taylor's



    ​​​​​1031926810​​​​​ at ​​​dblLinear(10000000)​​​ ​quokka.js:52:0​

    ​​​​​1: 1248.006ms​​​​​

    ​​​​​1031926810​​​​​ at ​​​dbl_linear2(10000000)​​​ ​quokka.js:55:0​

    ​​​​​2: 27667.439ms​​​​​





    share|improve this answer



























      up vote
      2
      down vote













      We have two functions:

      $Y(x) = 2 * x + 1$

      $Z(x) = 3 * x + 1$



      We need to apply these two functions to every value x in result



      I simply kept two running indices of result representing which x in result we have calculated so far for both the $Y$ function and $Z$ function. I called these values yIndex and zIndex.



      I then calculate Y(result[yIndex]) and Z(result[zIndex]) which I called yNext and zNext. I then append the smallest value of these two values to our result and then increment the yIndex or zIndex depending on which function gave the smaller value (or both if they are equal). Repeat until you reach desired n.



      This gives $O(n)$ time.



      +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
      | currentN | yIndex | zIndex | yNext | zNext | result | comment |
      +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
      | 0 | 0 | 0 | 1 | 1 | [1] | Base case, yNext = zNext = 1, increment both, append result |
      | 1 | 1 | 1 | 3 | 4 | [1,3] | calculate new yNext and zNext, yNext < zNext, increment yIndex only, append yNext |
      | 2 | 2 | 1 | 7 | 4 | [1,3,4] | calculate new yNext using result[yIndex of the previous row], zNext < yNext, increment zIndex only, append zNext |
      | 3 | 2 | 2 | 7 | 10 | [1,3,4,7] | ... yNext < zNext, increment yIndex |
      | 4 | 3 | 2 | 9 | 10 | [1,3,4,7,9] | ... |
      +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+



      Here is the algorithm:



      const tail = xs => xs[xs.length - 1]

      function dblLinear (n)
      const results =
      const YZ =
      yIndex: 0,
      zIndex: 0,
      get yNext () return (results[YZ.yIndex] ,
      get zNext () return (results[YZ.zIndex]


      do
      results.push(Math.min(YZ.yNext, YZ.zNext))
      YZ.yIndex += tail(results) === YZ.yNext
      YZ.zIndex += tail(results) === YZ.zNext
      while (results.length < n)

      return results.pop()



      Performance test between this implementation and Peter Taylor's



      ​​​​​1031926810​​​​​ at ​​​dblLinear(10000000)​​​ ​quokka.js:52:0​

      ​​​​​1: 1248.006ms​​​​​

      ​​​​​1031926810​​​​​ at ​​​dbl_linear2(10000000)​​​ ​quokka.js:55:0​

      ​​​​​2: 27667.439ms​​​​​





      share|improve this answer

























        up vote
        2
        down vote










        up vote
        2
        down vote









        We have two functions:

        $Y(x) = 2 * x + 1$

        $Z(x) = 3 * x + 1$



        We need to apply these two functions to every value x in result



        I simply kept two running indices of result representing which x in result we have calculated so far for both the $Y$ function and $Z$ function. I called these values yIndex and zIndex.



        I then calculate Y(result[yIndex]) and Z(result[zIndex]) which I called yNext and zNext. I then append the smallest value of these two values to our result and then increment the yIndex or zIndex depending on which function gave the smaller value (or both if they are equal). Repeat until you reach desired n.



        This gives $O(n)$ time.



        +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
        | currentN | yIndex | zIndex | yNext | zNext | result | comment |
        +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
        | 0 | 0 | 0 | 1 | 1 | [1] | Base case, yNext = zNext = 1, increment both, append result |
        | 1 | 1 | 1 | 3 | 4 | [1,3] | calculate new yNext and zNext, yNext < zNext, increment yIndex only, append yNext |
        | 2 | 2 | 1 | 7 | 4 | [1,3,4] | calculate new yNext using result[yIndex of the previous row], zNext < yNext, increment zIndex only, append zNext |
        | 3 | 2 | 2 | 7 | 10 | [1,3,4,7] | ... yNext < zNext, increment yIndex |
        | 4 | 3 | 2 | 9 | 10 | [1,3,4,7,9] | ... |
        +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+



        Here is the algorithm:



        const tail = xs => xs[xs.length - 1]

        function dblLinear (n)
        const results =
        const YZ =
        yIndex: 0,
        zIndex: 0,
        get yNext () return (results[YZ.yIndex] ,
        get zNext () return (results[YZ.zIndex]


        do
        results.push(Math.min(YZ.yNext, YZ.zNext))
        YZ.yIndex += tail(results) === YZ.yNext
        YZ.zIndex += tail(results) === YZ.zNext
        while (results.length < n)

        return results.pop()



        Performance test between this implementation and Peter Taylor's



        ​​​​​1031926810​​​​​ at ​​​dblLinear(10000000)​​​ ​quokka.js:52:0​

        ​​​​​1: 1248.006ms​​​​​

        ​​​​​1031926810​​​​​ at ​​​dbl_linear2(10000000)​​​ ​quokka.js:55:0​

        ​​​​​2: 27667.439ms​​​​​





        share|improve this answer















        We have two functions:

        $Y(x) = 2 * x + 1$

        $Z(x) = 3 * x + 1$



        We need to apply these two functions to every value x in result



        I simply kept two running indices of result representing which x in result we have calculated so far for both the $Y$ function and $Z$ function. I called these values yIndex and zIndex.



        I then calculate Y(result[yIndex]) and Z(result[zIndex]) which I called yNext and zNext. I then append the smallest value of these two values to our result and then increment the yIndex or zIndex depending on which function gave the smaller value (or both if they are equal). Repeat until you reach desired n.



        This gives $O(n)$ time.



        +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
        | currentN | yIndex | zIndex | yNext | zNext | result | comment |
        +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+
        | 0 | 0 | 0 | 1 | 1 | [1] | Base case, yNext = zNext = 1, increment both, append result |
        | 1 | 1 | 1 | 3 | 4 | [1,3] | calculate new yNext and zNext, yNext < zNext, increment yIndex only, append yNext |
        | 2 | 2 | 1 | 7 | 4 | [1,3,4] | calculate new yNext using result[yIndex of the previous row], zNext < yNext, increment zIndex only, append zNext |
        | 3 | 2 | 2 | 7 | 10 | [1,3,4,7] | ... yNext < zNext, increment yIndex |
        | 4 | 3 | 2 | 9 | 10 | [1,3,4,7,9] | ... |
        +----------+--------+--------+-------+-------+-------------+----------------------------------------------------------------------------------------------+



        Here is the algorithm:



        const tail = xs => xs[xs.length - 1]

        function dblLinear (n)
        const results =
        const YZ =
        yIndex: 0,
        zIndex: 0,
        get yNext () return (results[YZ.yIndex] ,
        get zNext () return (results[YZ.zIndex]


        do
        results.push(Math.min(YZ.yNext, YZ.zNext))
        YZ.yIndex += tail(results) === YZ.yNext
        YZ.zIndex += tail(results) === YZ.zNext
        while (results.length < n)

        return results.pop()



        Performance test between this implementation and Peter Taylor's



        ​​​​​1031926810​​​​​ at ​​​dblLinear(10000000)​​​ ​quokka.js:52:0​

        ​​​​​1: 1248.006ms​​​​​

        ​​​​​1031926810​​​​​ at ​​​dbl_linear2(10000000)​​​ ​quokka.js:55:0​

        ​​​​​2: 27667.439ms​​​​​






        share|improve this answer















        share|improve this answer



        share|improve this answer








        edited Jun 21 at 13:41


























        answered Jun 20 at 1:08









        Kyle Khoury

        212




        212






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f195788%2fcodewars-twice-linear-is-running-too-long%23new-answer', 'question_page');

            );

            Post as a guest













































































            Popular posts from this blog

            Chat program with C++ and SFML

            Function to Return a JSON Like Objects Using VBA Collections and Arrays

            Will my employers contract hold up in court?