22
\$\begingroup\$

A doubling sequence is an array of numbers where each subsequent number is at least twice the previous number.

Given an ordered list of numbers, determine if the numbers in the list (\$n_{x}\$) have the property that:

\$n_1 \times 2 \le n_2\$

\$n_2 \times 2 \le n_3\ ...\$

and so on until reaching the end of the list.

Input

A list of two or more numbers.

Output

Any distinct True or False value.

Examples:

[10,20,30] -> False
[10,20,40] -> True
[1,2,3] -> False
[1,2,4] -> True
[1,2,10] -> True
[1,1] -> False
[10,1] -> False
Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ Can input be sorted in either order? \$\endgroup\$
    – mabel
    Commented Feb 12, 2020 at 18:20
  • 1
    \$\begingroup\$ Pre-sorted in that it may be sorted ascending, descending, or some other order, but you don't have to change the order of the list that is fed to the function. \$\endgroup\$
    – atlasologist
    Commented Feb 12, 2020 at 18:20
  • \$\begingroup\$ Since inputs can be non-integers, do we care about floating point precision? Many of these solution fail for n_i+1 = n_i*(2-epislon) for some fairly large epsilons \$\endgroup\$
    – Vlo
    Commented Feb 12, 2020 at 19:40
  • 15
    \$\begingroup\$ what about negative numbers? what about the sequence of zeros? \$\endgroup\$
    – mazzy
    Commented Feb 12, 2020 at 20:03
  • \$\begingroup\$ "some other order" can be any reflexive transitive antisymmetric relation. In other words, your definition admits arbitrary order of the elements, which I'd guess is not what you intended. \$\endgroup\$
    – kyrill
    Commented Feb 12, 2020 at 22:19

49 Answers 49

Reset to default
1
2
1
\$\begingroup\$

StackCell, 16 bytes

:[{::+}x>?.:]'Y;

Explanation:

  • :[: Duplicate the top element of the stack, and then consume the duplicate. If it was non-zero, perform the loop body (up until the next ]) - else skip the loop body
  • {: Remove the top element of the stack, and place it in the 'cell' (temporary storage which is overwritten on writes and copied on reads)
  • ::+: Create two duplicates of the top element of the stack (previously the top-but-one element), and add them together to get 2x
  • }: Put the stored element back on the top of the stack
  • x: Swap the top two elements of the stack
  • >: Consume and compare the top two elements of the stack: If the top-most element is larger than the second-most element of the stack, push 1 to the stack, otherwise push 0 to the stack
  • ?: Consume the value on top of the stack, and skip the next instruction (.) if and only if the consumed value was 0
  • .: Halt the program immediately (falsy output)
  • :]: Duplicate the top value of the stack, then consume the duplicate. If it was non-zero, jump back to the instruction after the matching [; otherwise, continue
  • 'Y: Push the character Y to the stack, as a byte
  • ;: Print the top value of the stack, as a character
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Nekomata + -e, 4 bytes

∆$i≥

Attempt This Online!

-e      Check that
∆       the delta
   ≥    is greater than or equal to
 $i     the original list without the last item
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C (clang), 38 bytes

Returns 0 for doubling sequences, 1 otherwise.

f(*a,s){return--s?*a*2>*++a|f(a,s):0;}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala, 48 bytes

Golfed version. Try it online!

_.sliding(2).map{case Seq(a,b)=>b/a}.exists(_<2)

Ungolfed version. Try it online!

object Main {

  def f(x: List[Double]): Boolean = {
    x.sliding(2).map { case List(a, b) => b / a }.exists(_ < 2)
  }

  def main(args: Array[String]): Unit = {
    val data = List(
      List(10.0, 20.0, 30.0),
      List(10.0, 20.0, 40.0),
      List(1.0, 2.0, 3.0),
      List(1.0, 2.0, 4.0),
      List(1.0, 2.0, 10.0),
      List(1.0, 1.0),
      List(10.0, 1.0)
    )

    println(data.map(f))
  }
}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Desmos, 27 bytes


f(l)=\{l[2...]<2l,0\}.\max

Returns 0 for doubling sequences and 1 for non-doubling sequences.

Try It On Desmos!

Try It On Desmos! - Prettified

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal G, 3 bytes

¯>Ṫ

Try it Online!

A port of 05AB1E

Explained

¯>Ṫ
¯   # deltas
 >  # greater than original input
  Ṫ # last item removed
# G flag gets biggest item.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Kotlin, 50 bytes

{a:IntArray->(0..a.size-2).first{a[it]*2>a[it+1]}}

Try it online!

Int for false and Nothing for true (throws NoSuchElementException)

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 28 bytes

\d+
$*
((^|,(?=\3\3))(1+))+$

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

  ^|

On the first repeat, match at the beginning, otherwise...

    ,(?=\3\3)

... match a comma followed by a number which is at least twice as big as the previous match.

              (1+)

Capture the number so that it can be compared on the next repeat.

(                 )+$

All entries in the list need to satisfy the above conditions.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Clojure, 89 bytes

(fn[x](#(cond(empty? %)true(>=(first %)(* %2 2))(recur(rest %)(first %)):else false)x 0))

Try it online!

The obvious (and longest) solution to the problem.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -apl -MList::Util=reduce, 26 bytes

reduce{$_&&=$a<=$b/2;$b}@F

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Zsh, 29 bytes

(($1*2<=$2))&&${=3+$0 ${@:2}}

Try it online!

(($1*2<=$2))&&     # return false if 2 * $1 > $2
  ${=3+$0 ${@:2}}  # recursive call:
  ${ 3+         }  # if there is a third parameter
       $0 ${@:2}   # ... substitute the program name ($0), " ", "$2 $3 $4 "...
  ${=           }  # ... then split on spaces

In cases like a && or b ||, Zsh will simply return with the exit code of the previous command.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python 3, 52 bytes

lambda l:all(l[i-1]*2<=l[i]for i in range(1,len(l)))

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python 3, 52 bytes

lambda l:all(2*l[i]<=l[i+1]for i in range(len(l)-1))

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Extended), 18 bytes

∧/{(2ׯ1↓⍵)≤(1↓⍵)}

Try it online!

Decomposition/Explanation:

⍵ is the input vector (test cases). Output will be 1 or 0; 1 is TRUE/truthy, 0 is FALSE/falsey.

            (1↓⍵)  - Drop the first element from the input vector (call it LASTN)
      ¯1↓⍵         - Drop the last element from the input vector, separately, and
   (2×    )        - multiply it by two (call the result DFIRSTN)
           ≤       - compare corresponding elements - Each element of LASTN should be 
                     equal to or greater than the corresponding element of DFIRSTN.
  {              } - encapsulate as a dfn to apply to the input vector. This dfn will
                     return 0 for elements where the comparison is FALSE, 1 where TRUE
∧/                 - AND (Boolean conjunction) reduction of the vector. ∧/ A B C D ... is
                     equivalent to A ∧ B ∧ C ∧ D ∧ ..., and if there are any FALSE values
                     in the vector, the result will be FALSE (0)

The linked TIO has the test cases and a REPL; you can test your own vectors by changing the input field, one vector per line.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 51 bytes

r;f(a,l)int*a;{for(r=--l;l--;)r=*a*2>*++a?0:r;a=r;}

Pretty simple. For every element of the array, check if the current element times two is greater than the next element.

Returns zero if it is not a doubling sequence and non-zero (or more specifically the length minus one) otherwise.

-10 bytes thanks to ceilingcat!

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ @ceilingcat Thanks. I was trying to find a solution with no counter variable. \$\endgroup\$
    – S.S. Anne
    Commented Feb 14, 2020 at 20:28
  • \$\begingroup\$ 49 bytes \$\endgroup\$
    – ceilingcat
    Commented Feb 14, 2020 at 21:07
0
\$\begingroup\$

T-SQL, 64 bytes

This can handle positive values above 0

Returns -1 for true, 0 for false

SELECT~min(1/~x)FROM(SELECT a/lag(2*a)over(ORDER BY i)x FROM @)y

Try it online

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C++ (gcc), 75 71 67 65 bytes

int f(int*a,int s){int r=1;for(;--s;)r*=a[s]>=2*a[s-1];return r;}

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ @ceilingcat Thanks for the input! I thought the i++ placement was UB, so I dumped the variable - 67 bytes! \$\endgroup\$
    – Varad Mahashabde
    Commented Feb 23, 2020 at 15:24
  • \$\begingroup\$ @ceilingcat Should've thought of that! \$\endgroup\$
    – Varad Mahashabde
    Commented Mar 1, 2020 at 18:01
  • 1
    \$\begingroup\$ 64 \$\endgroup\$
    – ceilingcat
    Commented Dec 7, 2020 at 10:06
0
\$\begingroup\$

Rockstar, 101 100 bytes

listen to F
D's0
while F
listen to T
let R be F/T-.5
turn up R
let D be D or R
let F be T

say not D

Try it here (Code will need to be pasted in, with each input integer on an individual line)

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Thunno 2 S!, 4 bytes

Ṣ$ṫ<

Try it online! Link is to verify all test cases.

Explanation

Ṣ$ṫ<  # Implicit input
Ṣ     # Deltas of input
 $ṫ   # Input without last item
   <  # Compare the two lists
      # Check if the sum is 0
      # Implicit output
Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.