Leetcode marathon day 2

tomasmor42 — Sun, 05 Apr 2020 09:28:29 +0000

The task of the second day is the task of finding a happy number:

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.

First I was thinking (as usual) to try to implement it straightforwardly. Let's create a function that gives us the next iteration for a number:

    def square_sum(n):
        return sum([int(i)**2 for i in str(n)])

At first, I was thinking that if we have a number with one digit it would be the end of the calculations and implemented it like this:

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n < 10:
            return (n == 1)
        else:
            res = self.square_sum(n)
            return self.isHappy(res)

But quite fast I realised that this is not correct. Because if we have 7, for example, we will receive on the next step 49, which is not one digit.
But if we take another number as a threshold, like 3, it might work. But we actually don't need 3 only because 3^2 = 9 which is a one-digit number. We could use a higher threshold if it's not a happy number. And the lowest happy number is 7. So the final version is

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n < 7:
            return (n == 1)
        else:
            res = self.square_sum(n)
            return self.isHappy(res)

It's not in any way an optimal solution, but it's working and according to the benchmarks it's working pretty well.

Leetcode marathon and day 1

tomasmor42 — Fri, 03 Apr 2020 20:11:13 +0000

I was never a big fan of classical interview-tasks. Like, find the minimal size sub-array multiplied elements of which give a number sum of digits of which is a palindrome.
But these tasks for better or for worse are part of interviewing culture. And if I ever want to work in a big company (and currently not only big companies are using "smart" problems for an interview process) I probably will need to learn how to solve them. Or at least don't freak out I see them.
So I decided to participate in the Leetcode marathon. The marathon started on the 1st of April with compatibly easy tasks and during the month they suppose to be more complicated.

I'm a Python developer so all the tasks I'm going to implement in Python.

The first task was to find the first day was the following:

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?

A straightforward solution would be to go through the list and create a second structure one where we'll have numbers from the list and number of their appearances. With Python dictionary might be a good structure for it because we can search quite fast.

But authors of the problem definitely wanted something else. I was thinking about some mathematical expression, to multiply every number on something and take a sum or something. But I didn't come up with a nice mathematical formula, but I remembered about the XOR function. This binary function is only 1 when values are different. For integers comparison representations of values bit by bit. It means that for equal numbers we will have always 0 as a result.
It means that full function will look like:

class Solution(object):
    def singleNumber(self, nums):
        res = nums.pop(0)
        for i in nums:
            res = res ^ i
        return res

DEV Community: tomasmor42

Leetcode marathon day 2

Leetcode marathon and day 1