How many bystanders will help?

Question

Flavortext

The Bystander Effect is a phenomenon where individuals are less likely to help a victim if other people are present. The idea is that as there are more people around, the individual burden is less, and each individual thinks "someone else will help them", which results in the counterintuitive fact that fewer people will help when there are more people.

(This is why if you're in public and something bad happens and you / someone else needs help, you should address random individuals ("you in the red shirt") to help specifically rather than "someone please help" to bypass this psychological phenomenon)

Let's take a very simplified interpretation of this theory and assume everyone has a numerical threshold for helping.

Specification

A list of people will be given, each with a threshold to help. The threat level is 1. A person will help if and only if the threat level divided by the number of people in the crowd is greater than equal to their threshold. When a person decides to help, they leave the crowd. This means that the individual threat, which is the threat level (1) divided by the size of the crowd, is now higher as a result because the crowd is smaller.

The total threat level (1) never changes, for simplicity.

How many people end up helping?

Input

You are given a list of floating point numbers in any reasonable format. This list will be non-empty, and every number will be in the inclusive range from 0 to 1. You may assume the list is sorted in either order you would like.

Output

You are to output a single integer, indicating how many of the individuals decide to help.

Example

Consider the test case 0.2, 0.2, 0.3, 0.6, 0.8. The crowd has five people, so the threat to each individual is 0.2. Therefore, the first two people will help. Now, the crowd is 0.3, 0.6, 0.8. Since there are only three people, the threat to each individual is now 0.3. Therefore, the third person will now decide to help. The crowd is now 0.6, 0.8, so the individual threat is 0.5, and nobody decides to help anymore. Therefore, the final result is 3.

Test Cases

1                        -> 1
0.5, 0.8                 -> 2 # 0.8 initially won't help, but will when 0.5 leaves
0.2, 0.2                 -> 2 # both will help initially
0.2, 0.2, 0.3, 0.6, 0.8  -> 3 # 0.2 and 0.2 leaving prompts 0.3 to help, but the other two won't help
0, 0.25, 0.33, 0.5, 1    -> 5 # all of them help only after the previous person left, starting with 0
0, 0.25, 0.34, 0.34, 1   -> 2 # 0 and 0.25 help, but 0.34 is just a bit too indifferent to help, which means 1 will never help either
0.5, 0.5, 0.5            -> 0 # nobody helps. RIP

Reference Implementation

This implementation (Python) shows the final answer at the very end. It also breaks down the process stage-by-stage.

Answer 1

Jelly,  9 8  7 bytes

(Saved 1 when the assumption of sorted input was allowed, and another realising there was no need to floor the inverses.)

İ<Jṣ1ṪL

A monadic Link accepting a list of floating-point numbers in \$[0,1]\$ sorted in descending order that yields an integer.

Try it online! Or see the test-suite.

How?

Effectively this evaluates how many people need to be in the crowd to stop each person helping, identifies crowd sizes that would be too big for anyone to help if those most likely to help have been removed, then counts those in excess of the biggest of those crowd sizes.

İ<Jṣ1ṪL - Link: list of thresholds, T  e.g. [1, 0.34, .34, .25, 0]
İ       - inverse (T)                       [1, 2.94, 2.94. 4, inf]
  J     - range of length (T)               [1, 2, 3, 4, 5]
 <      - less than?                        [0, 0, 1, 0, 0]
   ṣ1   - split at ones                     [[0, 0], [0, 0]]
     Ṫ  - tail                              [0, 0]
      L - length                            2

---

Equivalently:

İ<JṚÄċ0
   Ṛ    - reverse                           [0, 0, 1, 0, 0]
    Ä   - cumulative sums                   [0, 0, 1, 1, 1]
     ċ0 - count zeros                       2

Answer 2

J, 13 bytes

-2 thanks to Jonah!

-&#(#~%<#)^:_

Try it online!

-&#(#~%<#)^:_
   (     )^:_ until result does not change
      %<#     (1 % element) smaller than length of the list
    #~        filter out other elements
-&#           length(original list) - length(filtered out list)

Answer 3

Jelly, 9 bytes

Lİ<SɗƬạLṪ

Try it online!

Does not assume sorted input. :/

Since shrinking the crowd never makes anyone not help, this calculates the new crowd size from the previous one until nobody new leaves.

     Ƭ       Loop until a fixed point, starting from
L            the length of the input:
  <Sɗ        how many elements of the input are strictly greater than
 İ           the reciprocal?
      ạL     Subtract each intermediate result from the length of the input,
        Ṫ    and return the last one.

Uses Ƭ ... Ṫ instead of ÐL because ÐL passes the previous left argument as the right argument rather than reuse the original right argument, given a dyad.

Answer 4

Jelly, 7 bytes

×JỊẠÐƤS

Try it online!

Assumes the input is sorted descendingly (thanks to @caird). 8 bytes without that assumption:

Jelly, 8 bytes

JU×ṢỊẠƤS

Try it online!

The idea here is that if we consider the sorted list, once anyone doesn't go, nobody after them will go either. Furthermore, considering an individual, they will only go if everyone before them went, so their individual condition for helping is 1/reversed_index > threshold, i.e. threshold * reversed_index < 1.

Thus:

JU       ' [len(l)..1], i.e. reversed index
  ×Ṣ     ' times the sorted values
    Ị    ' <=1
     ẠƤ  ' map 'all' over prefices, results in 1s over the prefix of helpers
       S ' sum

Answer 5

Charcoal, 16 13 bytes

ＩＬ⊟⪪⭆Ａ›×ι⊕κ¹1

Try it online! Link is to verbose version of code. Requires input sorted in descending order. Edit: Saved 3 bytes after following @DominicvanEssen's advice. Explanation:

     Ａ          Input array
    ⭆           Map over elements and join
          κ     Current index
         ⊕      Incremented
       ×        Multiplied by
        ι       Current value
      ›         Is greater than
           ¹    Literal `1`
   ⪪            Split on
            1   Literal string `1`
  ⊟             Pop last element
 Ｌ              Length
Ｉ               Cast to string
                Implicitly print

Answer 6

JavaScript (ES6), 39 bytes

Essentially the same answer as below but it assumes that the input is sorted from lowest to highest, which is now allowed.

a=>(n=a.length)-(a.map(k=>n-=k*n<=1),n)

Try it online!

---

JavaScript (ES6), 46 bytes

a=>(n=a.sort().length)-(a.map(k=>n-=k*n<=1),n)

Try it online!

Commented

a =>               // a[] = input
  ( n = a.sort()   // sort the input; although the sort is in lexicographical
                   // order, it's OK for floats in [0, 1]
        .length    // initialize n to the length of the array
  ) - (            //
    a.map(k =>     // for each value k in a[]:
      n -=         //   decrement n if:
        k * n <= 1 //     k * n is less than or equal to 1
    ),             // end of map()
    n              // subtract the new value of n from the original value
  )                //

Answer 7

R, 56 44 bytes

Edit: saved 12 bytes after looking at Jonathan Allan's answer: please upvote that!

function(c,d=sum(c|1))match(T,1/c<d:1,d+1)-1

Try it online!

Answer 8

Wolfram Language (Mathematica), 34 bytes

LengthWhile[#,l=Tr[1^#];1>=l--#&]&

Try it online!

Requires input to be sorted, least to greatest.

---

Iteratively, 35 bytes:

0//.x_:>Tr@UnitStep[x#-Tr[1^#]#+1]&

Try it online!

No sorting requirements.

Answer 9

Haskell, 33 bytes

f(x:y)|sum(x<$x:y)<=1=1+f y
f _=0

Try it online!

The relevant function is f, which takes as input the list of tolerances in increasing order.

How?

The only trick I think it's worth showcasing is the sum(x<$x:y) part. Its job is to compute x*length(x:y), but:

1. it's 2 bytes shorter, and
2. since x is a Double and length returns an Int, Haskell would complain if we tried to multiply them together; to fix this issue, the monstrosity we would need is x*toEnum(length$x:y), which is 9 bytes longer than sum(x<$x:y).

Answer 10

Jelly, 12 bytes

×Ị¥ÐḟL$ÐLLạL

Try it online!

×Ị¥ÐḟL$ƬẈ.ịI

Try it online!

×Ị¥ÐḟL$ƬẈạLṪ

Try it online!

Go upvote Jonathan Allan's or Unrelated String's answers, they're much better.

How they work

×Ị¥ÐḟL$ÐLLạL - Main link. Takes a list L on the left
      $ÐL    - Repeat the previous 2 links until it reaches a fixed point:
     L       -   Yield the length of the list
  ¥Ðḟ        -   Remove elements which return false under the previous 2 links:
 Ị           -     They are less than or equal to 1 when
×            -     multiplied by the length
         L   - Get the length of the fixed point
           L - Get the length of L
          ạ  - Absolute difference

×Ị¥ÐḟL$ƬẈ.ịI - Main link. Takes a list L on the left
      $Ƭ     - Repeat the previous 2 links until it reaches a fixed point. Return all steps:
     L       -   Yield the length of the list
  ¥Ðḟ        -   Remove elements which return false under the previous 2 links:
 Ị           -     They are less than or equal to 1 when
×            -     multiplied by the length
        Ẉ    - Lengths of each step
         .ị  - Get the first and last
           I - Subtract them

×Ị¥ÐḟL$ƬẈạLṪ - Main link. Takes a list L on the left
      $Ƭ     - Repeat the previous 2 links until it reaches a fixed point. Return all steps:
     L       -   Yield the length of the list
  ¥Ðḟ        -   Remove elements which return false under the previous 2 links:
 Ị           -     They are less than or equal to 1 when
×            -     multiplied by the length
        Ẉ    - Lengths of each step
          L  - Length of L
         ạ   - Absolute differences
           Ṫ - Get the last one

Answer 11

Python 2, ^{72 \$\cdots\$ 43} 42 bytes

Saved 7 bytes thanks to the man himself Arnauld!!!
Saved 3 4 bytes thanks to dingledooper!!!

f=lambda l:l>[]>1>=len(l)*l.pop()and-~f(l)

Try it online!

Assumes the input is sorted from highest to lowest.

Answer 12

Jelly, 13 bytes

>Lİ$x@ƊÐLL_@L

>Lİ$x@ƊÐLL_@L
>Lİ$          arg is greater than 1/len(arg)
    x@        filter (finds people left)
       ÐL     apply until converged
         L_@L length of argument minus length

Try it online!

Answer 13

Pyth, 15 bytes

l-Qu.xf<c1lGTGY

Test suite

Explanation:

l-Qu.xf<c1lGTGY  | Full program
l-Qu.xf<c1lGTGYQ | with implicit variables
-----------------+------------------------------------------------------------------------------
      f      G   | filter the list G for elements T such that
        c1lG     | 1 / length of G
       <    T    | is less than T
    .x        Y  | unless an error is thrown in which case return the empty list
   u           Q | repeat the above until a previous result is repeated, starting with the input
l-Q              | length of input with the elements of the resulting list removed