Missing Number Python

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        if nums[0] != 0:
            return 0        elif nums[-1] != len(nums):
            return len(nums)

        for i in range(0, len(nums)):
            if i != nums[i]:
                return i


Time Complexity : O(nlogn) // sorting
Space Complexity : O(1)

Missing Number Python

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

// Using Extra space Hash set

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        seen_set = set(nums)
        for i in range(0,len(nums)+1):
            if i not in seen_set:
                return i



Time Complexity : O(n)
Space Complexity : O(n)

Missing Number Python

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
        for i in range(0,len(nums)):
            missing ^= i ^ nums[i]
        return missing



Time Complexity : O(n)
Space Complexity : O(1)

Note : Here array starts with 0 not 1 so n = len(nums) 

if it starts with 1 like natural numbers then n = len(nums)+1

Missing Number Python

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity ?

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = int((n*(n+1))/2)
        for i in nums:
            total_sum-=i
        return total_sum


Time Complexity : O(n)
Space Complexity : O(1)

Note : Here array starts with 0 not 1 so n = len(nums) 

if it starts with 1 like natural numbers then n = len(nums)+1

Happy Number Python

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Method 2 : Floyd's Cycle Finding Algorithm

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit ** 2            return total_sum

        slow_runner = get_next(n)
        fast_runner = get_next(slow_runner)
        while fast_runner != 1 and slow_runner != fast_runner:
            slow_runner = get_next(slow_runner)
            fast_runner = get_next(get_next(fast_runner))

        return fast_runner == 1
Time Complexity : O(logn)
Space Complexity : O(logn)

Happy Number Python

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Python Solution :

Method 1 : Detecting the loop with Hashset

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit ** 2            return total_sum

        seen = set()
        n = get_next(n)
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)
        return n == 1        Time Complexity : O(log(n))
    
    Space Complexity : O(log(n))

Single Number in Python

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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

Example 2:

Input: [4,1,2,1,2]

Output: 4

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = nums[0]
        for i in range(1, len(nums)):
            result = result ^ nums[i]
        return result

TIme Complexity : O(n)
Space Complexity : O(1)