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)

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Java Solution : O(n) space and O(n) time complexity

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        Set<ListNode> nodeSeen = new HashSet<>();

        while(head !=null){

            if(nodeSeen.contains(head))

                return true;

            else

                nodeSeen.add(head);

            head=head.next;

        }

        return false;

    }

}

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

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        ListNode fast = head;

        ListNode slow = head;

        while(fast!=null&&fast.next!=null){

            slow = slow.next;

            fast = fast.next.next;

            if(slow==fast)

                return true;

        }

        return false;

    }

}

ValueError: need more than 2 values to unpack

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: need more than 2 values to unpack

Solution :

No of variables should be equal to no of elements in sequence or tuple.

Example :

data = [25,"Satya","G",(8,31,2010)]
age,fname,lname,dob = data
print("My name ",fname+lname," and age ",age," dob ",dob)
age,fname,lname,(month,day,year) = data
print("My name ",fname+lname," and age ",age," and year i born :",year)

Single Number - LeetCode

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

Java Solution :

class Solution {
    public int singleNumber(int[] nums) {
        if(nums == null) return 0;
        int result = 0;
        for(int i=0;i<nums.length;i++){
            result ^= nums[i];
        }
        return result;
    }
}