Problem 1855. Usage of java.math : N Choose K with unlimited precision

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/image","targetMode":"","relationshipId":"rId1","target":"/media/image1.png"}],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Calculate the binomial coefficient nchoosek with full accuracy. This challenge may use the wonderful word of java.math that allows unlimited precision calculations. The primary reference sites are</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html\"><w:r><w:t>Java Math</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html\"><w:r><w:t>Java BigDecimal</w:t></w:r></w:hyperlink><w:r><w:t>, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html\"><w:r><w:t>Java BigInteger</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The usage of BigDecimal functions add, multiply, and divide may be required.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Java Math:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[vd-decimal value, vstr-string, vi-integer value \nxBD=java.math.BigDecimal(vd); % valid vd,vstr,vi creates xBD a BigDecimal variable\nimport java.math.*; % simplifies statements\nxBD=BigDecimal(vstr);\nxplusyBD=xBD.add(BigDecimal(y)); % add input requires BD type\nxmultiplyzBD=xBD.multiply(BigDecimal(z)); % multiply input requires BD type\nxdividezBD=xBD.divide(BigDecimal(z)); % divide input requires BD type\nxmultydivz=xBD.multiply(yBD).divide(zBD); out=x*y/z\n\nTo convert java to string of unlimited length can be achieved via java toString or Matlab char\n\nxstr=toString(xBD) or xstr=char(xBD)]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [N,K] [ Inputs to nchoosek(N,K) 0&lt;=K&lt;=N&lt;200 ]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> C (char variable of C=nchoosek(n,k) or BigDecimal variable type )</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Theory:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Binomial_coefficient\"><w:r><w:t>C(n,k)</w:t></w:r></w:hyperlink><w:r><w:t> link shows multiple evaluation methods.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>C(n,k)= n!/(k!(n-k)!)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:customXml w:element=\"image\"><w:customXmlPr><w:attr w:name=\"height\" w:val=\"-1\"/><w:attr w:name=\"width\" w:val=\"-1\"/><w:attr w:name=\"relationshipId\" w:val=\"rId1\"/></w:customXmlPr></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The factorial method gives a direct solution while the multiplicative may require fewer operations.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Hint:</w:t></w:r><w:r><w:t> C(5,3)=(5/3)*(4/2)*(3/1)= (5/1)*(4/2)*(3/3); numerator has k terms</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Future Challenges:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>1.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow\"><w:r><w:t>Usage of java.math</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[2. nchoosek_large (full precision)\n3. Next Prime\n4. factor_large]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>5.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1854-factorial-unlimited-size-java-math\"><w:r><w:t>Factorial</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"},{"partUri":"/media/image1.png","contentType":"image/png","content":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAiQAAAA6BAMAAABynl+BAAAAMFBMVEX///9iYmIEBASenp5AQEAwMDCKioq2trYiIiJ0dHQMDAzm5uYWFhZQUFDMzMwAAAAm8IwaAAAAAXRSTlMAQObYZgAACIxJREFUeNrtWmtsVMcVPnv3ce0uXtutCKW08aKoeRWSjairFJritCQ/EkRXalOaWA0kCqWgAAsCpIAqFvEjVaq0C1FABLXZKMqPqE1rU9OkqaLYNJES+lolQQgiipUoEaY1YIMB26y3M2fu3fs6M95ZbygyPtLdvd5v5juzZ2fOnDufASalRbphyrxW31Z9X2NyhqSUnAqJz0aWPjsVEq9t+V1yYgT94q1r8uSrz384sf6Jv4n3WLaqfHW9DNijhPdUzBXqVVCQNLBji/IbXz/ekF63XR6Wk9QtlyExEomzEEY7JLD5wdMWWhHXTwBOnpc5oGgAzjbWKyLC3CR+FfiNZ7i43rVvpjXJc86rsnz1Cb2Y2YxLpCXweqjrFmglXNjwgswBRQOJbMMeRUi4m0Z/9OM3WVwsvTa8Wt66ZlSRrzZQHx54lL0MhiXwv6D0TYFWwnWReTajMgcUDQxmz61ShIS7yfhDOXTU4drmTL0vV5Gv6Lwb5XmpVQLPZQMQaCVc03g6yUsdtOonT+7mSxTQas2SJU68Ps3JWNY/L8u7ipx8TAKzSR1GtCKun/Psk5c5IGjGLW25m9UyPohA7DaWbxoHnjn4Els5REgeOTNzzqz0mpb6iyTA60RxF+xaTBUYbJM79i1IDCNK1JxBrkEekmTn4x+TDggaapiB0nbDk7E3U+70Y7bnBJcBkQfYb9Z/90petJWIPH37B2YmmciN/ZIEINJk3wVteDmHbXLPqOYj6i9+SK67+cpvPzGXdkDQUMP0uzGjvz/nCWXpUsHiMmATa9/6xkzAkHUGGMPt7+XCVL4SAFxos++InbuNw2Vyd4K7B1Gf0VyPsWvfWGY97YCgoYbpcwMjHUdMz/56a7FgcYVgMS9aF/bAjXwhbesMzMJwf5Px8B/OYtsgkG8csO/Y5MMC5yCfpdGtbMGGFnZz2CY/jXN9On/9612IQryPJc83t1s3bi6n8Vk29KdiGZzdQQd4ecqFonN/R4EaHHdT98JSbOG4OdOTFlwR6OQx3Htz4jDf53Z8OxDmz+WgvycfAgkAHWn7Do6s5J//xdOKwRZ5AtHLuF382ob/zK7RXErcuLhcjePsWteS4WmOchBInpufGjnIbxaNbiw4w3T3ZW7Mk08+AZ4x9dn5JhLGIqgPSm9jiIO1M0u5/WnyARyBcymnySz/BCsgbJEP/rYMNOfNYY7C0PfZX/eCdePicjWex1a+MYBLj3CAl6e++MX8++7B8UV2ucfv9OVuMi2nwDumJRYfGCGcZ9+AYoEvrdK/g4txOfwjRK5SBOpy8iahNMI2uVNQb4EYov7UQHKxX3PkJcj+iXZA0HS4tiqKkLvZl74U9+Tl8KF6i8uI8cCEhyHaznfruksBt6kcPPAaFRIBjCbpJjxRRZs4XCYv2+btzW8h6jOaaz8vS4r5Y7QDgma88XM3q+HYmKfWieV2WVwGvsbSMHYjT2BDYwFKtke/v5TyJYBIB9Wk4aFWXu7mOFwmL9sfT5/+KqL+TZjkWsCA1MjOAu2AoBlv/NzNd2Fvgzcr1z9rc23zMv5dtxSM5+XYGiW8pkKu15UOCJplwyLXndUeMnIZSS++QzckQy/KsdlKeHaFXPellBSzoXZDRi6jzXveUOjVdbBJipj7VTCilXCZaRUFRVPtkC2u73k/fT6jyx+WpreoEo5WzHWHygFBM97CkY5JcBnzvJ8WtM9Yiw/LkN1KeHfFXId7FRS7qzhZlY1JcIUOeuvVhbN5bom8g0XdncFei3E37cpebefP7hEve87EWTLQVB3VSd9u34zUX5e17+qCq9LkI9a2gI6ThWvdIr6/Mzt9HzQ6SSokA/7PFlKBmsNkiy3iO/rJ+VfmQEiSSwZCV2su8X5H7WFGfM8m3dnMtZ5LIsd9HxSu8UwS/43hW2qpGoZEKVxqKqNXznYYOSzoy3pgR1BPRCx+iwarxbYiKREu16Iy+p2gConK6FpC0qz9cpWpeEPHjW4sVwezVppNJQONELus84gs2BKnAL4Y2OTXsSjU83LwRN7xatvqOVu7BeoL1fmarw9pGVc00mJUth64gGjEMbNOxyGyqYVLUoWUKKPxHyZrHZKhozLkeCTZgzf7PhUfzCIacayo9Tshm5nDE0Kv3R/dyl4/Yteqlx2vtvXD8GWB+p7mR69cLvmZURQr19ID44uJRhwb0polyKYWLkkVUqaMXknLG5fEoDfEm/leMxojGiE2V4cWe1jC5Veo9ZqyVEjhtWy2MvqZf+/EdPkhiGHgmbytB44NEwcriG3XcCh6qIVLUoWUKaN6lsZlZoIpb4Jypywk0RJ/s/VA6t+ABHaTxphED7VwSaqQMmVUawK0puNHOsB8BsLyCgflTln1OvQ0hnQsAzz7H3iB+M0Re0NnlmCPt9m3zRwBLjO5hEu08xloSJe9utFFdyHqKKP80rLzhwBufgLuXAHRn+6VffF3udwpfRL+pJdvlkIPhC8Q6VBgB3RCgj3GES4dFdKFBpVRVEd1bEw85/WoH/f60orDgX2PQFkPhHaqyEBMpzIQPdTCpUuFdKFBZfTezya/LlEdIZW+BmU9sP6fVJGBWF6nLMEeauGSVCFlymjNDeVOaUgu7oeyHhiaThYZDIu/rFWWcDa1cEmqkDJlNHDSNVFDuVMaEtjl6IE/oo6gBJbVcCh6qIVLUoWUKaOHX/xxR01DIuROqTl7XvyGWrpVC5dayqie/df+Yr3VhYutq/L/xY28UsuQqIVLLWVUz1qsxXGoeooN9qR8vLbP39K1ZvJ5+ZoSrcnqqHqWwE4rnYV/UNvn705p6cCrr/ubVOhEDvOWTDCS/CFso3WWUWMZQilc6imjOramLr6IWRtMWdmSE184k8zqJ3i2EJl8ISn1xeezPPWf7qn1Uk6v11m7RcuDU8Gojf0PBYku0k/USjQAAAAASUVORK5CYII="}]}

Calculate the binomial coefficient nchoosek with full accuracy. This challenge may use the wonderful word of java.math that allows unlimited precision calculations. The primary reference sites are <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html">Java Math</a>, <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html">Java BigDecimal</a>, and <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html">Java BigInteger</a>.The usage of BigDecimal functions add, multiply, and divide may be required.Java Math:<pre class="language-matlab">vd-decimal value, vstr-string, vi-integer value 
xBD=java.math.BigDecimal(vd); % valid vd,vstr,vi creates xBD a BigDecimal variable
import java.math.*; % simplifies statements
xBD=BigDecimal(vstr);
xplusyBD=xBD.add(BigDecimal(y)); % add input requires BD type
xmultiplyzBD=xBD.multiply(BigDecimal(z)); % multiply input requires BD type
xdividezBD=xBD.divide(BigDecimal(z)); % divide input requires BD type
xmultydivz=xBD.multiply(yBD).divide(zBD); out=x*y/z
</pre><pre class="language-matlab">To convert java to string of unlimited length can be achieved via java toString or Matlab char
</pre><pre class="language-matlab">xstr=toString(xBD) or xstr=char(xBD) 
</pre>Input: [N,K] [ Inputs to nchoosek(N,K) 0&lt;=K&lt;=N&lt;200 ]Output: C (char variable of C=nchoosek(n,k) or BigDecimal variable type )Theory:<a href = "http://en.wikipedia.org/wiki/Binomial_coefficient">C(n,k)</a> link shows multiple evaluation methods.C(n,k)= n!/(k!(n-k)!)<img src = "http://upload.wikimedia.org/math/b/1/a/b1a5828ee5ec18a1362999a76f3c63e6.png">The factorial method gives a direct solution while the multiplicative may require fewer operations.Hint: C(5,3)=(5/3)*(4/2)*(3/1)= (5/1)*(4/2)*(3/3); numerator has k termsFuture Challenges:1. <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow">Usage of java.math</a><pre class="language-matlab">2. nchoosek_large (full precision)
3. Next Prime
4. factor_large
</pre>5. <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1854-factorial-unlimited-size-java-math">Factorial</a>

Solve

Solution Stats

71 Solutions
40 Solvers

Last Solution submitted on Sep 04, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 335235

1 Comment

1 Comment

James on 17 Oct 2013

I forgot to check nchoosekJava(1,1) :-(

Problem Recent Solvers40

Problem Tags

bigdecimal java nchoosek

Problem 1855. Usage of java.math : N Choose K with unlimited precision

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers40

Suggested Problems

More from this Author236

Problem Tags

Problem 1855. Usage of java.math : N Choose K with unlimited precision

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers40

Suggested Problems

More from this Author236

Problem Tags

Players