Title: fix(maths): prevent intermediate integer overflow in CatalanNumbers by Bhumit267 · Pull Request #7732 · TheAlgorithms/Java · GitHub
Open Graph Title: fix(maths): prevent intermediate integer overflow in CatalanNumbers by Bhumit267 · Pull Request #7732 · TheAlgorithms/Java
X Title: fix(maths): prevent intermediate integer overflow in CatalanNumbers by Bhumit267 · Pull Request #7732 · TheAlgorithms/Java
Description: I have read CONTRIBUTING.md. This pull request is all my own work -- I have not plagiarized it. All filenames are in PascalCase. All functions and variable names follow Java naming conventions. All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations. All new algorithms include a corresponding test class that validates their functionality. All new code is formatted with clang-format -i --style=file path/to/your/file.java Description In CatalanNumbers.java, catalan(n) computes the $n$-th Catalan number using the factorial formula: $$\frac{(2n)!}{(n+1)! \cdot n!}$$ Previously, factorial(int n) used standard 64-bit signed long arithmetic. Because $21!$ and higher overflow 64-bit long (where 20! is $\approx 2.43 \times 10^{18}$ and Long.MAX_VALUE is $\approx 9.22 \times 10^{18}$), computing $(2n)!$ for any $n \ge 11$ ($2n \ge 22$) caused silent integer overflow, resulting in incorrect and negative results (e.g. catalan(11) evaluated to -65 instead of 58786). Changes Updated factorial(int n) to use BigInteger internally to prevent intermediate integer overflow during multiplication. Kept the public API signature public static long catalan(final int n) unchanged. Added validation for $n > 35$ (throwing IllegalArgumentException) because $C_{35} = 3,116,285,494,907,301,262$ is the maximum Catalan number representable within a signed 64-bit long ($C_{36} > \text{Long.MAX_VALUE}$). Updated CatalanNumbersTest.java with test cases for $n = 11$, $n = 15$, and boundary value $n = 35$, along with testing invalid inputs ($n = 36$). Verification mvn test -Dtest=CatalanNumbersTest passes (15/15 tests passing). mvn checkstyle:check passes with 0 violations.
Open Graph Description: I have read CONTRIBUTING.md. This pull request is all my own work -- I have not plagiarized it. All filenames are in PascalCase. All functions and variable names follow Java naming conventions. ...
X Description: I have read CONTRIBUTING.md. This pull request is all my own work -- I have not plagiarized it. All filenames are in PascalCase. All functions and variable names follow Java naming conventions. ...
Opengraph URL: https://github.com/TheAlgorithms/Java/pull/7732
X: @github
Domain: github.com
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react-reconciler,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@d5750093facf |
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:08b1d153-79bc-3049-4b46-39a6e878a60c |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | ACC2:226200:355DFC9:4786E83:6AFA972C |
| html-safe-nonce | fc84b1703d5106fe60b8cf5f9edf76b5a80df59f69aef46478677533bed2d35d |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJBQ0MyOjIyNjIwMDozNTVERkM5OjQ3ODZFODM6NkFGQTk3MkMiLCJ2aXNpdG9yX2lkIjoiNjQ3ODA4MzU3NTAzMDM4ODUyNCIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | 128b1261372c7db2936736fab14f113fa714bfc4ba37444a407dfc95f54aedb0 |
| hovercard-subject-tag | pull_request:5194017750 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/TheAlgorithms/Java/pull/7732/files |
| twitter:image | https://avatars.githubusercontent.com/u/178378365?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/178378365?s=400&v=4 |
| og:image:alt | I have read CONTRIBUTING.md. This pull request is all my own work -- I have not plagiarized it. All filenames are in PascalCase. All functions and variable names follow Java naming conventions. ... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 612d3e6ffd693e7ea8d9fcf452370995872baef31d825b1fedef704cd3d24ac7 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/TheAlgorithms/Java git https://github.com/TheAlgorithms/Java.git |
| octolytics-dimension-user_id | 20487725 |
| octolytics-dimension-user_login | TheAlgorithms |
| octolytics-dimension-repository_id | 63477660 |
| octolytics-dimension-repository_nwo | TheAlgorithms/Java |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 63477660 |
| octolytics-dimension-repository_network_root_nwo | TheAlgorithms/Java |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 072e34035c13c31543fba9f025cbbbda4210dae4 |
| ui-target | canary-2 |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width