Integers with multiple sum of two cubes

Hash Table Sorting Counting Enumeration

55.7% acceptance

May 13, 2026

You are given an integer n. An integer x is considered good if there exist at least two distinct pairs (a, b) such that: a and b are positive integers. a <= b x = a3 + b3 Return an array containing all good integers less than or equal to n, sorted in ascending order.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_good_integers(n: i32) -> Vec<i32> {
    use std::collections::HashMap;
    let mut counts: HashMap<i32, u8> = HashMap::new();
    let n64 = n as i64;
    let max_a = ((n64 as f64).cbrt() as i64) + 2;
    for a in 1..=max_a {
      let a3 = a * a * a;
      if a3 > n64 { break; }
      for b in a..=max_a {
        let s = a3 + b * b * b;
        if s > n64 { break; }
        let e = counts.entry(s as i32).or_insert(0);
        if *e < 2 { *e += 1; }
      }
    }
    let mut ans: Vec<i32> = counts.into_iter()
      .filter(|(_, c)| *c >= 2)
      .map(|(k, _)| k)
      .collect();
    ans.sort_unstable();
    ans
  }
}