CODEWITHSUNDEEP
rust
Gudarzi
Gudarzi

Reputation: 575

How do I return the sum of the three largest elements in an array?

I'm trying to return sum of 3 largest numbers in an array like this:

fn max_tri_sum(arr: &[i32]) -> i32 {
    arr.sort();
    arr[0]+arr[1]+arr[2]
}

but I keep getting this error:

error[E0596]: cannot borrow `*arr` as mutable, as it is behind a `&` reference

fn max_tri_sum(arr: &[i32]) -> i32 {
                   ------ help: consider changing this to be a mutable reference: `&mut [i32]`

    arr.sort();
       ^^^ `arr` is a `&` reference, so the data it refers to cannot be borrowed as mutable

I shouldn't change arr: &[i32] to arr: &mut [i32] because of some restrictions. So what can I do about it?

P.S: I tried to clone arr to a mutable variable but got other errors:

fn max_tri_sum(arr: &[i32]) -> i32 {
    let a: &mut [i32] = *arr.clone();
    a.sort();
    a[0]+a[1]+a[2]
}

Upvotes: 2

Views: 1136

Answers (2)

ShadowMitia
ShadowMitia

Reputation: 2533

In Rust, you can't have a variable that has both reference and mutable reference in the same scope.

You have several choices :

  • You could simply do a loop on the slice to get the values you want. Something like this (there's probably a more elegant way with iterators)
    fn max_tri_sum(arr: &[i32]) -> i32 {
    let mut maxes = [0, 0, 0];
    for &el in arr {
        if el > maxes[0] && el < maxes[1] {
            maxes[0] = el;
        } else if el > maxes[1] && el < maxes[2] {
            if maxes[1] > maxes[0] {
                maxes[0] = maxes[1];
            }
            maxes[1] = el;
        } else if el > maxes[2] {
            if maxes[2] > maxes[1] {
                maxes[1] = maxes[2];
            }
            maxes[2] = el;
        }
    }

    maxes[0] + maxes[1] + maxes[2]
    }
  • You can create a new Vec from the slice, and then do all the operations on it (which requires allocation, but should be fine for small Vecs).
    fn max_tri_sum(arr: &[i32]) -> i32 {
        let mut arr = Vec::from(arr);
        arr.sort();
        arr[0] + arr[1] + arr[2]
    }

I would also like to point that sort sorts from smallest to biggest, so the index 0, 1, 2, ... would be the smallest values in the array, which I don't think is what you want to do!

Upvotes: 1

akuiper
akuiper

Reputation: 215077

You could also use a BinaryHeap to store the three largest values so far and replace the smallest value while looping through the array:

use std::collections::BinaryHeap;

fn max_tri_sum(arr: &[i32]) -> i32 {
    let mut heap = BinaryHeap::new();
    heap.push(-arr[0]);
    heap.push(-arr[1]);
    heap.push(-arr[2]);
    
    for e in arr[3..].iter() {
        if -e < *heap.peek().unwrap() {
            heap.pop();
            heap.push(-e);
        } 
    }
    -heap.drain().sum::<i32>()
}

Or if you prefer the sort option, you can convert the slice to a vector:

fn max_tri_sum(arr: &[i32]) -> i32 {
    let mut arr1 = arr.to_vec();
    arr1.sort_by(|a, b| b.cmp(a));
    arr1[0] + arr1[1] + arr1[2]
}

Playground

Upvotes: 2

Related Questions