1+ lines Ruby, Python, Java, C++


  • 51

    Several different solutions, some with O(1) extra space, some with O(n).


    Sum of 0..n minus sum of the given numbers is the missing one.

    These only use O(1) extra space.

    Ruby

    def missing_number(nums)
      (n = nums.size) * (n+1) / 2 - nums.reduce(:+)
    end
    

    Python

    def missingNumber(self, nums):
        n = len(nums)
        return n * (n+1) / 2 - sum(nums)
    

    Java

    public int missingNumber(int[] nums) {
        long n = nums.length;
        return (int) (n * (n+1) / 2 - IntStream.of(nums).sum());
    }
    

    C++

    int missingNumber(vector<int>& nums) {
        long n = nums.size();
        return n * (n+1) / 2 - accumulate(begin(nums), end(nums), 0);
    }
    

    Using long for Java and C++ to prevent overflow (the n*(n+1) overflows ints already for n=46341, and then the /2 causes an actual wrong result).


    Xor-ing the given numbers and 0..n.

    These use O(n) extra space, but I like them anyway.

    Ruby

    def missing_number(nums)
      nums.zip(1.step).flatten.reduce(:^)
    end
    

    Python

    def missingNumber(self, nums):
        return reduce(operator.xor, nums + range(len(nums)+1))
    

    Xor-ing with O(1) space

    Saw this from ts before. Xoring 0..n results in [n, 1, n+1, 0][n % 4]. You can also spot the pattern by looking at xors of such ranges, and it's easy to explain as well.

    Ruby

    def missing_number(nums)
      n = nums.size
      nums.reduce(:^) ^ [n, 1, n+1, 0][n % 4]
    end
    

    Python

    def missingNumber(self, nums):
        n = len(nums)
        return reduce(operator.xor, nums) ^ [n, 1, n+1, 0][n % 4]
    

    Sum, without formula.

    Java and C++:

        int miss = 0, i = 0;
        for (int num : nums)
            miss += ++i - num;
        return miss;
    

    In Java I believe this is safe, overflow might happen but not cause a wrong result (because another overflow will fix it). In C++ I believe it's probably safe in the same way, except that that behavior isn't defined in the standard(s) but is a de-facto standard anyway. In any case, I could just use 64-bit ints again to be safe.


    Set/array difference

    Don't know about Ruby's runtime, might not be linear. Python's sets are hash sets and the difference is linear time on average. Don't know about its worst case, and apparently neither does the TimeComplexity page.

    Ruby

    def missing_number(nums)
      ((0..nums.size).to_a - nums)[0]
    end
    

    Python

    def missingNumber(self, nums):
        return (set(range(len(nums)+1)) - set(nums)).pop()

  • 0

    Hi, Stefan, just a side comment. You rank the 1st among all users now :-)


  • 0

    woohoo... Congrats Stefan, well deserved :)


  • 0

    Good, I can finally retire :-P


  • 0

    Just kidding.


  • 0

    @jianchao.li.fighter Congrats for passing Shangrila as well now :-)


  • 0

    @StefanPochmann Haha, long time no see~ Well, both Shangrila and me have not been here for just too long.


  • 0

    @jianchao.li.fighter I just sit quietly and listen to your conversation.


  • 0
    T

    @StefanPochmann, you are amazing. Python set operation is genius.
    Although series sum operation might not work for array like this
    [555, 1000, 1200, 1, 0].


  • 0

    @trimal said in 1+ lines Ruby, Python, Java, C++:

    Although series sum operation might not work for array like this
    [555, 1000, 1200, 1, 0].

    Well that input is invalid...


  • 0
    T

    @StefanPochmann This is problem statement

    "Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array."

    If I understand that correctly, array could have any number from 0 to n, it doesn't have to be sorted.


  • 0

    @trimal Yes, any number from 0 to n. But n is 5.


  • 0
    T

    @StefanPochmann maybe I understood it wrong. Recently I was asked this question for technical interview. Interviewer stated array could have any number and I should be able to find next missing positive integer.


  • 0

  • 0
    J

    Very helpful as alway.
    I'm still learning lambda and steam. Is there a stream expression that equivalent to this for loop solution?

    public int missingNumber(int[] nums) {
            int n = nums.length;
            for(int i = 0; i < nums.length; i ++){
                n = n^i^nums[i];
            }
            return n;
        }
    

    Thank you in advance!


  • 0
    G
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.