23
\$\begingroup\$

Sometimes I see a claim like "80% of respondents agreed" and I think "what was your sample size? 5?" because, of course, with a sample size of 5 it's possible to get 80% to agree on something. If the claim is "47% of respondents agreed" then I know it must be a larger sample size.[1]

challenge

Given a positive integer x≤100, output the minimum number of respondents needed for an honest claim that "x% of respondents agreed".

Input and output will be however integers (or numbers) are normally handled.

This is code golf.

Caveat: Note the effect of rounding. For example, a claim of "12% of respondents agreed" can mean that there were 8 respondents, 1 agreed, and the claim is rounding half down. Likewise, "13% of respondents agreed" can mean there were 8 respondents, 1 agreed, and the claim is rounding half up. Assume numbers closest to an integer are rounded to that integer, but you must account for both of ways of rounding half. Thus, on an input of 12 or of 13, your algorithm should output 8.

examples

  • 1 ↦ 67
  • 2 ↦ 40
  • 100 ↦ 1

[1] Of course, this is assuming that what I'm reading is telling the truth.

\$\endgroup\$
7
  • \$\begingroup\$ How is the minimum number of respondents calculated? \$\endgroup\$
    – lyxal
    Dec 4, 2023 at 12:59
  • 13
    \$\begingroup\$ I think this is A239525 without the first term. \$\endgroup\$
    – Arnauld
    Dec 4, 2023 at 14:13
  • 1
    \$\begingroup\$ Do standard floating-point error tolerance apply? For instance with python's Fraction module I get abs(Fraction(13,100).limit_denominator(8) - 13/100) = 0.0050000000000000044 which rejects 8 as a valid sample size for 13% because the difference is above a half-percent. \$\endgroup\$
    – Stef
    Dec 4, 2023 at 22:48
  • 1
    \$\begingroup\$ @Stef as noted in the question post, on an input of 13, the output should be 8. \$\endgroup\$
    – msh210
    Dec 5, 2023 at 0:00
  • \$\begingroup\$ Related: Convert a decimal to a fraction, approximately \$\endgroup\$
    – tsh
    Dec 5, 2023 at 2:12

12 Answers 12

9
\$\begingroup\$

K (ngn/k), 27 bytes

**&~`i$(199*%/:/&=69)-1.99*

Try it online!

Based on the formula from the OEIS entry:

Find the smallest N such that there is some x > 0 with abs(100*x/N - n) <= 0.5.

For golfing reasons this actually checks -1 < 1.99*(100*x/N - n) < 1, which happens to be equivalent on the domain of the problem.

\$\endgroup\$
5
  • \$\begingroup\$ Why the 1.99 instead of 2 (or 2.0)? \$\endgroup\$
    – justhalf
    Dec 5, 2023 at 5:47
  • \$\begingroup\$ @justhalf Because I need the strict comparison. K has no absolute value function, so what I'm doing for this check is round_to_zero(1.99*(100*x/N - n)) == 0 \$\endgroup\$
    – ovs
    Dec 5, 2023 at 7:19
  • \$\begingroup\$ Ah, so it's actually checking -1 <= 1.99*(100*x/N - n) <= 1 in the code? The explanation in the last paragraph seems to already include the strict comparison, so I was confused. \$\endgroup\$
    – justhalf
    Dec 5, 2023 at 7:25
  • \$\begingroup\$ No, it is strict. With 2* you would need <= comparison. For example with n=12: 1.99*(100*1/8 - 12)=0.995<1, 2*(100*1/8 - 12)=1<=1 \$\endgroup\$
    – ovs
    Dec 5, 2023 at 8:33
  • 1
    \$\begingroup\$ Ah, ok, because round_to_zero checks for <1, got it. It would still work if the code were -1 <= 1.99*(100*x/N - n) <= 1, right (that's what I meant in previous comment). \$\endgroup\$
    – justhalf
    Dec 5, 2023 at 9:44
7
\$\begingroup\$

Jelly,  14  12 bytes

-2 thanks to Nick Kennedy! (Make a 100 by 100 table with values over 100% rather than a triangle of values.)

ạȷ2÷þפḤỊ§TḢ

A monadic Link that accepts a positive integer from \$[1,100]\$, the reported percentage, and yields another positive integer, the minimal number of respondents.

Try it online! Or see all 100.

How?

ạȷ2÷þפḤỊ§TḢ - Link: positive intger from [1..100], P
      ¤      - nilad followed by link(s) as a nilad:
 ȷ2          -   10^2 -> 100
    þ        -   {[1..100]} x {[1..100]} table of:
   ÷         -     divide
     ×       -   multiply by {100} (vectorises)
                 -> [[100],[50.0,100],[33.33,66.66,100],[25.0,50.0,75.0,100],...]
ạ            - {P} absolute difference (vectorises) {that}
       Ḥ     - double (vectorises)
        Ị    - is insignificant? (vectorises) - i.e. abs(x)<=1
         §   - sums
          T  - truthy indices
           Ḣ - head
\$\endgroup\$
2
  • \$\begingroup\$ ạȷ2÷þפḤỊ§TḢ saves two at the expense of lower efficiency (generates 10000 percentages rather than 5050). \$\endgroup\$ Dec 4, 2023 at 23:12
  • 1
    \$\begingroup\$ Good call, thanks! \$\endgroup\$ Dec 5, 2023 at 1:04
5
\$\begingroup\$

C (gcc), 56 bytes

i;j;f(n){for(i=j=1;fabs(100.*j/i-n)>.5;j=--j?:++i);j=i;}

Try it online!

\$\endgroup\$
5
\$\begingroup\$

JavaScript (Node.js), 45 bytes

x=>g=i=>(x-i%69/(y=i>>7)*100)**2<.26?y:g(-~i)

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Vyxal 3, 14 bytes

₅Dᵒ÷×ṚTȧd1≤ᶤaꜝ

Try it Online!

Takes an integer argument and returns an integer argument. This is a Vyxal 3 translation of @JonathanAllan’s Jelly answer. It’s two bytes longer, partly because the outer modifier returns the result in the transposed reverse of what is needed for this problem.

₅Dᵒ÷×ṚTȧd1≤ᶤaꜝ­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌­
₅               # ‎⁡100
 D              # ‎⁢Triplicate
  ᵒ÷            # ‎⁣Outer divide by using (100..1),(100..1)
    ×           # ‎⁤Multiply (by 100)
     Ṛ          # ‎⁢⁡Reverse
      T         # ‎⁢⁢Transpose
       ȧ        # ‎⁢⁣Absolute difference with main input
        d       # ‎⁢⁤Double
         1≤     # ‎⁣⁡Less than or equal to 1
           ᶤa   # ‎⁣⁢Find first where any true
             ꜝ  # ‎⁣⁣Increment by 1
💎

Created with the help of Luminespire.

\$\endgroup\$
4
\$\begingroup\$

APL+WIN, 35 bytes

Prompts for input:

⌊/(⎕=(⌈n-.5),⌊.5+n←100×÷m)/m,m←⍳100

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
4
\$\begingroup\$

Python 3, 85 72 bytes

-13 bytes since I saw answers to other questions use a function

lambda x:[a for a in range(68)for b in range(a)if abs(x-100*b/a)<=.5][0]

try it online!, or see all the numbers

pre-golf:

x=int(input())
for a in range(68):        # for all denominators (starting from lowest)
 for b in range(a):        # and numerators (bonus, doesn't let /0 through)
  if abs(x-100*b/a)<=.5:   # is it within rounding range, up or down?
   print(a)                # then print the denominator
   exit()                  # anything else will be bigger

credit to oeis for sequence and formula

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 15 bytes

∞.ΔтLт*s/α2zs@à

Try it online or verify all outputs.

Explanation:

∞                # Push an infinite positive list: [1,2,3,...]
 .Δ              # Pop and find the first/smallest that's truthy for:
   тL            #  Push a list in the range [1,100]
     т*          #  Multiply each by 100: [100,200,...,10000]
       s/        #  Divide each by the current integer
         α       #  Get the absolute difference of each with the (implicit) input
          2zs@   #  Check for each whether it's <= 0.5:
          2      #   Push 2
           z     #   Pop and push 1/2
            s    #   Swap so the list is at the top
             @   #   >= check
              à  #  Pop and check if any in the list is truthy
                 # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 15 bytes

∞.ΔDÝs/т*α2zs@à

Try it online!

Explanation:

∞        Push infinite list
.Δ       Find first item in list where:
    D    Duplicate item
    Ý    Create an array 0-N
    s/   Switch last two and divide
    т*   Multiply by 100
    α    Absolute difference (input is automatically in stack)
    2zs  Push 0.5 before the last item
    @    Compare 0.5 with list (>=)
à        Check if the list contains 1
\$\endgroup\$
8
  • \$\begingroup\$ @Arnauld Thank you for the response! I didn't notice this previously, I believe that this only works when n in the formula used (see other responses) is 1. \$\endgroup\$
    – Flummox
    Dec 4, 2023 at 15:53
  • \$\begingroup\$ @Arnauld I fixed the bug. I'm now tied with the other 05AB1E answer, but that doesn't work for 0 so I think I still win. \$\endgroup\$
    – Flummox
    Dec 4, 2023 at 18:15
  • \$\begingroup\$ Note that the question states the input will be a "positive integer ≤ 100", i.e. nonzero \$\endgroup\$
    – noodle man
    Dec 5, 2023 at 2:48
  • \$\begingroup\$ @noodleman Yes. But based on the challenge explanation, logically it should contain. My solution runs faster and supports 0 as an input so I believe that I won. \$\endgroup\$
    – Flummox
    Dec 5, 2023 at 14:33
  • 1
    \$\begingroup\$ @Flummox "Winning" doesn't really mean anything here anymore; we're all here to have a good time, no need to worry about whose solution is "better". \$\endgroup\$
    – Ginger
    Dec 5, 2023 at 17:03
2
\$\begingroup\$

Charcoal, 24 bytes

NθI⌊Φφ∧ιΦφ¬‹·⁵↔⁻θ∕×λ¹⁰⁰ι

Try it online! Link is to verbose version of code. Very slow as it does about 1,000 times as much work as necessary. Explanation: Uses the OEIS formula.

Nθ                          First input as a number
     φ                      Predefined variable `1000`
    Φ                       Filter on implicit range
       ι                    Current value
      ∧                     Logical And
         φ                  Predefined variable `1000`
        Φ                   Filter on implicit range
                   λ        Inner value
                  × ¹⁰⁰     Multiplied by `100`
                 ∕          Divided by
                       ι    Outer value
              ↔⁻            Absolute difference with
                θ           Input number
          ¬‹·⁵              Is less than or equal to `0.5`
   ⌊                        Take the minimum
  I                         Cast to string
                            Implicitly print
\$\endgroup\$
1
\$\begingroup\$

R, 53 bytes

f=\(n,x=1)`if`(all(abs(n-100*(1:x)/x)>.5),f(n,x+1),x)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

AWK, 66 bytes

{for(;i++<99;)for(j=0;j++<r=i;)if(.5>=(n=$1-100*j/i)&&n>=-.5)next}

Try it online!

\$\endgroup\$

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.