#Improve leetcode score

19 messages · Page 1 of 1 (latest)

shadow frigate
#

Got a lousy score, any clue on how to improve it ?

Question:
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

My sol:

use std::collections::HashMap;

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut hm = HashMap::new();
        
        for val in nums.iter(){
            match hm.insert(val,val){
                
                Some(val) => hm.remove(&val),
                Some(_) => hm.remove(&val),
                None => hm.insert(val,val),
                
            };
        }
        let vec:Vec<&i32> = hm.into_keys().collect();
        *vec[0]
    }
}

https://leetcode.com/problems/single-number/

shadow frigate
#

using brute force via for loop is quicker but still not the best score

impl Solution {
    pub fn single_number(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let mut i = 0;
        for val in nums.iter() {
            if i+1 == nums.len() {return nums[i]}
            else if nums[i] == nums[i+1] {
                i+=2
            }
            else{return nums[i]}
        } 
       0
    }
}
analog frost
#

key is "and use only constant extra space."

#

extra hint, you can do it with just nums and a single extra i32 (you can also do it without any extra storage, but it's not really any different)

#

extra extra hint, you should look for an operation on i32 where f(f(x)) = x, or in other words an operation that returns the state to the same if applied twice, but tells you the number if you only apply it once

shadow frigate
#

and use only constant extra space
yeah wasnt sure what this meant xD

#

guess it means not to create a new var

tough wagon
#

constant space means not dependent on the size of the input

#

so you can have a variable or 2 or 10

#

but a HashMap/HashSet/Vec that doesn't have a bounded amount of elements is not "constant space"

#

(yes, technically Vec of size 2**30 is a constant, but that's abuse of the requirements)

analog frost
shadow frigate
river gale
shadow frigate
#

dont feel bad for looking at the top solution, since I would not have come up with that

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        
        let mut result = 0;
        
        for num in nums {
            result ^= num;
        }
        
        result
        
    }
}
river gale
shadow frigate
#

i dont know why, im still getting 5-6ms, whereas it should 0ms

river gale
#

luck of the draw 🤷‍♂️ LeetCode measurements aren't very exact

#

I submitted the fold solution a couple times and got variances of a couple ms and a couple tenths of a mb