So I think I was able to get this with an exact calculation. I thought it was going to turn out to be pretty convoluted, but I guess it's not. I think got it right, at least:

#!/usr/bin/perlusev5.24;usestrict;usewarnings;usefeatureqw(signatures);nowarnings"experimental::signatures";useCarp;useList::Utilqw(sum0);usePOSIXqw(ceil);sub cola( $n, @queue ) {my$q_len=@queue;my$i=0;my$last_idx=@queue;$last_idx+=((2**++$i)*@queue)while($n>$last_idx);my$prev_last_idx=$last_idx-((2**($i))*@queue);my$nth_can=ceil(($n-$prev_last_idx)/2**$i)-1;return$queue[$nth_can];}my@queue=qw(Sheldon Leonard Penny Rajesh Howard);useTest::Moretests=>4;is(cola(4,@queue),"Rajesh");is(cola(6,@queue),"Sheldon");is(cola(12,@queue),"Rajesh");is(cola(27,@queue),"Penny");

Benchmarking with timethis in Benchmark got me this result:

Basically, I just keep track of how many nodes there are in a tree structure which represents the doubling of the people in the queue. In each level of the tree, you double the number of nodes in the level before it, but we want the running total so far (which I call $last_index above because that is the index of the last node in the level where the $nth cola would be).

Once you figure out which "level" of the tree the $nth cola would be, you get the last index of the level before so that you can zero out the current level and any indices there. That makes it easy to figure out "where" on the current level of the tree the $nth cola is, and you just divide by the depth of the tree so far to turn that into an index that works on the initial array. Subtract one to get the 0-index value into the original array.

Edit Looks like Corey figured out the same thing, but with more math.

## re: Daily Challenge #17 - Double Trouble VIEW POST

TOP OF THREAD FULL DISCUSSIONSo I think I was able to get this with an exact calculation. I thought it was going to turn out to be pretty convoluted, but I guess it's not. I

thinkgot it right, at least:Benchmarking with

`timethis`

in`Benchmark`

got me this result:Basically, I just keep track of how many nodes there are in a tree structure which represents the doubling of the people in the queue. In each level of the tree, you double the number of nodes in the level before it, but we want the running total so far (which I call

`$last_index`

above because that is the index of the last node in the level where the`$n`

th cola would be).Once you figure out which "level" of the tree the

`$n`

th cola would be, you get the last index of the levelbeforeso that you can zero out the current level and any indices there. That makes it easy to figure out "where" on the current level of the tree the`$n`

th cola is, and you just divide by the depth of the tree so far to turn that into an index that works on the initial array. Subtract one to get the 0-index value into the original array.EditLooks like Corey figured out the same thing, but with more math.