3
\$\begingroup\$

It is Restricted Integer Partitions, but with maximum number.

Question

Three positive integers are given. First number is number to divide, second number is length of partition, and third number is maximum number. First number is always largest, and bigger than other two.

For example, 5, 2, 3. Then, make partition of 5 which have 2 parts, and maximum number you can use is 3. Note that you don't have to use 3 : maximum number can be 2 or 1.

In this case, there is only one partition : 3, 2.

Partition is unordered : which means 3 + 2 and 2 + 3 is same.

But in case like 7, 3, 3, there are two partition : 3, 3, 1 and 3, 2, 2.

To make it sure, You can use third number as largest number, but you don't have to use it. So 5, 4, 3 is true.

Question is : Is there are more than one partition, given length and maximum number?

Output is True or 1 or whatever you want when there is only one partition, and False or 0 or whatever you want where there are more than one partition, or no partition.

Winning condition

This is code golf, so code with shortest byte wins.

Examples

Input -> Output

7, 6, 2 -> True (2+1+1+1+1+1) : 1 partitions
5, 4, 4 -> True (2+1+1+1) : 1 partitions
5, 4, 3 -> True (2+1+1+1) : 1 partitions
5, 4, 2 -> True (2+1+1+1) : 1 partitions
5, 3, 2 -> True (2+2+1) : 1 partitions
7, 2, 3 -> False no partitions
7, 2, 2 -> False no partitions
7, 2, 1 -> False no partitions
9, 5, 3 -> False (3+3+1+1+1), (3+2+2+1+1), (2+2+2+2+1) : 3 partitions
6, 3, 3 -> False (3+2+1), (2+2+2) : 2 partitions
\$\endgroup\$
  • \$\begingroup\$ Are the input number guaranteed to be positive integers? \$\endgroup\$ – xnor May 26 at 6:34
  • \$\begingroup\$ Ah, I forgot that. Yes. \$\endgroup\$ – LegenDUST May 26 at 6:35
  • \$\begingroup\$ It would be good for the challenge to have test cases that include subtle cases where a solution might fail. Also, I'd suggest saying that you're talking about unordered partitions, meaning the 2+3 and 3+2 don't count as two different partitions. \$\endgroup\$ – xnor May 26 at 6:38
  • \$\begingroup\$ @xnor I added some examples, but I couldn't find subtle cases. \$\endgroup\$ – LegenDUST May 26 at 6:49
  • \$\begingroup\$ How do you get 7, 6, 2 -> True? With dividing 7 into 6 parts, I only see 2+1+1+1+1+1. Also, you say that the first number is always the largest, but it's not with 2, 7, 3. \$\endgroup\$ – xnor May 26 at 6:51
7
\$\begingroup\$

Python 2, 38 bytes

lambda n,k,m:m>n-k<2or-1<k*m-n<2+2/m*k

Try it online!

Characterizes the cases where there's only one legal partition.

Consider the partitions of \$n\$ into exactly \$k\$ parts each between \$1\$ and \$m\$ inclusive. There's only two ways to for there to be only one such partition.

  • The number \$n\$ is close to as small as possible (\$n=k\$ or \$n=k+1)\$ or as large as possible (\$n=mk-1\$ or \$n=mk)\$ for such a partitions. This leave only enough "wiggle room" for only one partition in each case:
    • \$n=1+1+\cdots +1+1\$.
    • \$n=2+1+\cdots+1+1\$.
    • \$n=m+m+\cdots+m+(m-1)\$.
    • \$n=m+m+\cdots+m+m\$.
  • We allow only \$m=2\$ maximum, forcing a unique partition made of 1's and 2's. Such a partition requires \$k \leq n \leq 2k\$.

The challenge lets us assume that \$n>k\$, so we can omit the \$n=k\$ case and \$k \leq n\$ check, and, as feersum observed, can let us check \$n=k+1\$ as \$n<k+2\$. The \$m=1\$ case makes it impossible to make a partition with \$n>k\$, so we make sure it's always rejected. This gives the condition

\$n \in \{ k+1, mk-1, mk\}\$and \$ m>1\$, or \$n \leq 2k \$ and \$m=2\$

\$\endgroup\$
  • 1
    \$\begingroup\$ n-k==1 can be n-k<2. \$\endgroup\$ – feersum May 27 at 8:25
  • \$\begingroup\$ @feersum Thanks, edited. \$\endgroup\$ – xnor May 27 at 21:21
2
\$\begingroup\$

Wolfram Language (Mathematica), 39 38 bytes

-1: first argument > other arguments (no length-1 partitions)

1==Tr[1^IntegerPartitions[#,{#2},#3]]&

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Ah, wolfram language. There is always built-in to solve something about math. Nice one. \$\endgroup\$ – LegenDUST May 26 at 7:24
2
\$\begingroup\$

05AB1E, 8 bytes

ÅœIù€à@O

Try it online!

Outputs truthy when there’s exactly one partition, falsy otherwise. (All numbers except 1 are falsy in 05AB1E, which makes this convenient).

Ŝ                    # integer partitions of the first input
  Iù                  # keep only those with length equal to the second input
    ۈ                # take the maximum of each one
      @               # test if the third input >= each one
       O              # sum
\$\endgroup\$
2
\$\begingroup\$

Jelly, (10?) 11 bytes

Œṗṁ«⁵ɗƑƇL⁼1

A full program which accepts N numberOfParts maximalSizeOfAnyPart as arguments and prints 1 if exactly one solution exists and 0 otherwise.

Try it online!

How?

Œṗṁ«⁵ɗƑƇL⁼1 - Main Link: N, numberOfParts
Œṗ          - integer partitions (of N)
       Ƈ    - keep those (P) for which:
      Ƒ     -   is invariant under:
     ɗ      -     last three links as a dyad - i.e. f(P, numberOfParts):
  ṁ         -       mould (P) like (numberOfParts)
    ⁵       -       3rd argument (maximalSizeOfAnyPart)
   «        -       minimum (vectorises)
        L   - length
          1 - literal one
         ⁼  - equal?
            - implicit print

If we may print 1 if exactly one solution exists and 0 OR nothing otherwise then Œṗṁ«⁵ɗƑƇMỊ is a 10 byte full program.

\$\endgroup\$
  • \$\begingroup\$ Minor comment: « is minimum. \$\endgroup\$ – Nick Kennedy May 27 at 22:41
  • \$\begingroup\$ Thanks Nick, fixed up the commentary. \$\endgroup\$ – Jonathan Allan May 27 at 23:50
1
\$\begingroup\$

Jelly, 7 bytes

œċ§ċ⁵=1

Try it online!

A full program taking the arguments in the order maximum part, number of parts, sum (i.e. reversed from original question).

Explanation

œċ      | Combinations with replacement (using maximum part size and number of parts)
   §    | Sum (vectorises)
    ċ⁵  | Count occurrences of desired integer from question
     =1 | Check if equal to 1
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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