Missing Test Case - 2709. Greatest Common Divisor Traversal #20747
Description
LeetCode Username
spejamchr
Problem number, title, and link
- Greatest Common Divisor Traversal https://leetcode.com/problems/greatest-common-divisor-traversal
Category of the bug
- Problem description
- Solved examples
- Problem constraints
- Problem hints
- Incorrect or missing "Related Topics"
- Incorrect test Case (Output of test case is incorrect as per the problem statement)
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
- Editorial
- Programming language support
Description of the bug
For programs that factor using a list of on-demand-generated primes, the program might miss some higher factors if the list of primes does not start out with enough primes.
Language used for code
Rust
Code used for Submit/Run operation
impl Solution {
pub fn can_traverse_all_pairs(nums: Vec<i32>) -> bool {
if nums.len() == 1 {
return true;
}
let mut primes = primes();
let mut possible_factors: Vec<i32> = primes.keys().cloned().collect();
possible_factors.sort();
let mut factor_sets = UnionFind::new(0);
let mut used_factors = std::collections::HashSet::new();
let mut first_factor = 0;
for num in nums {
let factors = factorize(num, &mut primes, &possible_factors);
if factors.len() == 0 {
return false;
}
first_factor = factors[0];
used_factors.insert(factors[0]);
for factor in factors.into_iter().skip(1) {
used_factors.insert(factor);
factor_sets.union(
*primes.get(&first_factor).unwrap(),
*primes.get(&factor).unwrap(),
);
}
}
used_factors.into_iter().all(|f| {
factor_sets.is_same_set(
*primes.get(&first_factor).unwrap(),
*primes.get(&f).unwrap(),
)
})
}
}
fn factorize(
mut n: i32,
primes: &mut std::collections::HashMap<i32, usize>,
possible_factors: &Vec<i32>,
) -> Vec<i32> {
if n == 1 {
return Vec::new();
}
if primes.contains_key(&n) {
return vec![n];
}
let mut factors = Vec::new();
for prime in possible_factors {
if prime.pow(2) > n {
break;
}
if n % prime == 0 {
while n % prime == 0 {
n /= prime;
}
factors.push(*prime);
}
}
if n != 1 {
factors.push(n);
if !primes.contains_key(&n) {
primes.insert(n, primes.len());
}
}
factors
}
#[derive(Debug)]
struct UnionFind {
parents: Vec<usize>,
ranks: Vec<usize>,
}
/// Non-standard implementation specific to this problem
impl UnionFind {
fn new(count: usize) -> Self {
Self {
parents: (0..count).into_iter().collect(),
ranks: vec![0; count],
}
}
fn find(&mut self, x: usize) -> usize {
while x >= self.parents.len() {
self.parents.push(self.parents.len());
self.ranks.push(0);
}
let mut x = x;
while x != self.parents[x] {
let tmp = x;
x = self.parents[tmp];
self.parents[tmp] = self.parents[x];
}
x
}
fn is_same_set(&mut self, x: usize, y: usize) -> bool {
self.find(x) == self.find(y)
}
fn union(&mut self, x: usize, y: usize) {
let mut x = self.find(x);
let mut y = self.find(y);
if x == y {
return;
}
if self.ranks[x] < self.ranks[y] {
let tmp = x;
x = y;
y = tmp;
}
if self.ranks[x] == self.ranks[y] {
self.ranks[x] += 1;
}
self.parents[y] = x;
}
}
fn primes() -> std::collections::HashMap<i32, usize> {
let max = 100; /// **ISSUE HERE** the max should be floor(sqrt(100000)) = 316
let mut all_nums: Vec<usize> = vec![0; max];
let mut n = 2;
while n < all_nums.len() {
if all_nums[n] == 0 {
let mut v = 2 * n;
while v < all_nums.len() {
all_nums[v] = n;
v += n;
}
}
n += 1;
}
(2..max)
.filter(|i| all_nums[*i] == 0)
.enumerate()
.map(|(i, v)| (v as i32, i))
.collect()
}Expected behavior
The given submission should have failed, but was accepted. The submission fails on this test case: [99221, 98587]
(Should be true, as the numbers share the factor 317: [317 * 313, 317 * 311]).