math: uniquePaths and leastCommonMultiple return non-integers below 2^53; iterative Euclid is subtraction-based and can hang
評価
- 難易度
- 3/5
- 見積もり時間
- 1〜2日
- 初心者へのやさしさ
- 35/100
- issue の種類
- バグ
- 明瞭さ
- 明確に書かれている
- 活発さ
- 停滞
- 技術スタック
- javascript
調査の方向性
The issue points to pascalTriangle, dpUniquePaths, leastCommonMultiple, and euclideanAlgorithmIterative, and compares the iterative Euclidean implementation with the recursive % version in the same folder. Read those implementations and their existing tests, then reproduce the reported inputs. Done means the three functions return the stated correct results and the iterative algorithm handles large inputs promptly; an open pull request is already linked.
索引モデルが issue の本文から書いたものです。
説明
Three small issues in the same family. All the true results fit safely in a JS number.
uniquePaths(23, 36)returns3489348548829780.5(a non-integer).uniquePaths(29, 29)returns7648690600760441, butdpUniquePathsgives the correct7648690600760440. Cause:pascalTrianglemultiplies before dividing, so the intermediate product exceeds 2^53. 25 wrong grids up to 40×40.leastCommonMultiple(549533988, 76324165)returns2747669939.9999995; expected2747669940. Cause:Math.abs(a * b) / gcdoverflows before dividing. Fix:Math.abs(a / gcd * b).euclideanAlgorithmIterativeuses repeated subtraction, which takes O(max/min) steps.(1e8, 1)takes about 1 s and(2**53 - 1, 2)effectively never finishes, while the recursive%version in the same folder takes under 1 ms. Fix: use%.
Found during an independent property-based audit of this repo (full report and reproducible harness: https://github.com/devladpopov/algorithm-autopsy/tree/main/autopsy-02).
- 主要言語
- JavaScript
- スター
- 197k
- フォーク
- 31k
- PR マージ指標
- 30日以内にマージされた PR はありません
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートなし
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
trekhleb/javascript-algorithms のほかの issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
trekhleb/javascript-algorithms#2231 ·
-
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
trekhleb/javascript-algorithms#2225 ·
-
BinarySearchTreeNode removing対応中かも @bbonch が 260 日前に担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
trekhleb/javascript-algorithms#2102 · コメント 1 件 ·
-
Trie.deleteWord fails for words containing characters outside the BMP (e.g. emoji)対応中かも @Shubham-Padkonde が 3 日前に担当しました。 オープン
難易度 1/5 1時間未満 初心者へのやさしさ 35/100
trekhleb/javascript-algorithms#2237 ·
-
bellmanFord: runs in O(V²·E) rather than the O(V·E) / O(E) stated in README対応中かも @Shubham-Padkonde が 3 日前に担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 35/100
trekhleb/javascript-algorithms#2236 ·
trekhleb/javascript-algorithms の issue をすべて見る
似ている issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
メンテナーはふだん 1 日以内に返信
-
Query Log shows "Upstream" for CNAME cloaking, schedule, NXDOMAIN hijack and response IP blocksオープンbug good first issue query-log web
難易度 2/5 1〜3時間 初心者へのやさしさ 85/100
ferrous-networking/ferrous-dns#326 ·
メンテナーはふだん 1 日以内に返信
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 67/100
Ylianst/MeshCentral#8294 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
メンテナーはふだん 1 日以内に返信
-
enhancement good first issue help wanted
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
yunaremaia/jsonl-cli#1 · コメント 1 件 ·