Multiply numbers from two iterators in order and without duplicates

user_612202 0
Viewed 59

I have this code and I want every combination to be multiplied:

fn main() {
  let min = 1;
  let max = 9;

  for i in (min..=max).rev() {
      for j in (min..=max).rev() {
          println!("{}", i * j);
      }
  }
}

Result is something like:

81
72
[...]
9
72
65
[...]
8
6
4
2
9
8
7
6
5
4
3
2
1

Is there a clever way to produce the results in descending order (without collecting and sorting) and without duplicates?

rust multiplication iterator
1 Answers

Note that this answer provides a solution for this specific problem (multiplication table) but the title asks a more general question (any two iterators).

The naive solution of storing all elements in a vector and then sorting it uses O(n^2 log n) time and O(n^2) space (where n is the size of the multiplication table). You can use a priority queue to reduce the memory to O(n):

use std::collections::BinaryHeap;
fn main() {
    let n = 9;
    let mut heap = BinaryHeap::new();
    for j in 1..=n {
        heap.push((9 * j, j));
    }
    let mut last = n * n + 1;
    while let Some((val, j)) = heap.pop() {
        if val < last {
            println!("{val}");
            last = val;
        }
        if val > j {
            heap.push((val - j, j));
        }
    }
}

playground. The conceptual idea behind the algorithm is to consider 9 separate sequences

  • 9*9, 9*8, 9*7, .., 9*1
  • 8*9, 8*8, 8*7, .., 8*1
  • ...
  • 1*9, 1*8, 1*7, .., 1*1

Since they are all decreasing, at a given moment, we only need to consider one element of each sequence (the largest one we haven't reached yet). These are inserted into the priority queue which allows us to efficiently find the maximum one. Once we have printed a given element we move onto the next one in the sequence and insert that into the priority queue. By keeping track of the last element printed we can avoid duplicates.

user_53041240
Related