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)

Unique Email Addresses in Python

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain '.'s or '+'s.

If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name.  For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address.  (Note that this rule does not apply for domain names.)

If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com.  (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list.  How many different addresses actually receive mails? 

Input: ["test.email+alex@leetcode.com", "test.e.mail+bob.cathy@leetcode.com",

 "testemail+david@lee.tcode.com"]
Output: 2Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com"actually
receive
mails

Example Note:

• 1 <= emails[i].length <= 100
• 1 <= emails.length <= 100
• Each emails[i] contains exactly one '@' character.
• All local and domain names are non-empty.
• Local names do not start with a '+' character.

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        seen = set()
        for email in emails:
            local, domain = email.split('@')
            if '+' in local:
                local = local[:local.index('+')]
            seen.add(local.replace('.', '') + '@' + domain)
        return len(seen)

Time Complexity : O(n)

Space Complexity : O(n)