Two Solutions in C# - O(1) and Boolean Array


  • 0
    J

    Two solutions - the first is O(1) in space. I get drastically different run-times from the OJ after repeat runs, so although I expect the first to be faster it isn't always (only one loop; no array allocation; less addition).

    I expected to get a little more benefit by using the formula for sum of the first n natural numbers. My thought is that my expensive operation is the loop through the array and that I'm still using the loop even if I'm using the formula. If so, it shows how fast adding n numbers is.

    Any insight?

        public int MissingNumber(int[] nums) {
            
            int n = nums.Length;
            var summation = (n * (n+1))/2;
            var actualSum = 0;
            
            for(int i = 0; i< nums.Length; i++)
            {
                actualSum += nums[i];
            }
            
            return summation - actualSum;
            /*
            var n2 = new bool[nums.Length+1];
            
            for(int i = 0; i < nums.Length; i++)
            {
                n2[nums[i]] = true;
            }
            
            for(int j = 0; j < n2.Length; j++)
                if (n2[j] == false)
                    return j; //nums[j];
                    
            return 1;
            */
        }
    

Log in to reply
 

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