# Posts

• ## Leetcode: Happy number

Write an algorithm to determine if a number `n` 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. 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. Return `true` if `n` is a happy number, and `false` if not.
For example, the number `19` is divided into `1^2` and `9^2`, then added together as `82`, then divided again, etc. After some iterations this reaches `100` which is `1^2 + 0^2 + 0^2 = 1`. On the other hand, `2` keeps ever incremententing. The programming aspect is relatively easy to solve in Python when converting the types to a string and then converting the string to a list.

• ## Leetcode: Linked list cycle

Given the head of a linked list, determine if there is a cycle in the list. A cycle is defined as a chain of arbitrary length that point to the same node. As an added difficulty, the solution should have a space complexity of `O(1)`. The first observation is that the cycle can be of arbitrary length. Thus, saving the visited nodes in a set would have a space complexity of `O(n)`. Secondly, the numbers cannot be compared because numbers might be duplicated throughout the list. Instead, we need to compare the list objects themselves.

• ## Leetcode: Contains duplicate

Given an array of `nums`, return `True` if there is a duplicated number and `False` otherwise. The simple most solution I could find was to use a `set` and then see for every number if it is already contained in the set. A map would have worked as well. The time complexity for this is `O(n)`, assuming that the access to the hash set is `O(1)`, it takes only one iteration over the whole list.

• ## Leetcode: Move zeros

The task is as follows: Given an integer array `nums`, move all 0’s to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array. The last note is actually the important part. Without this, it would be easy to just use array splitting in Python and add a zero. This would look similar to this:

This obviously overrides `nums` and the change is no longer in place. The next best solution that I found was to delete the items at position I from the list and then add a zero to the end. It is important to note, that the index needs to be decremented by one in case a `0` is found to account for double `0`. The number of steps needs to always be increased.

• ## Leetcode: Reverse string

Reverse a string and only use one extra variable. The solution is straightforward with two pointers, `p1` and `p2`. THe idea here is to start from both ends and increment `p1` and decrement `p2` until both of them meet in the middle. To switch the values of variables without assigning a temporary variable, the notation of `a, b = b, a` can be used. To convert a string into a list of characters, surroung the string with `[*s]`.

Page: 10 of 28