Skip to content

Instantly share code, notes, and snippets.

@cameronmoreau
Last active August 23, 2019 00:49
Show Gist options
  • Save cameronmoreau/e9ee755c187cba972271870d31f90b4b to your computer and use it in GitHub Desktop.
Save cameronmoreau/e9ee755c187cba972271870d31f90b4b to your computer and use it in GitHub Desktop.

Lucky Numbers

Ticket numbers usually consist of an even number of digits. A ticket number is considered lucky if the sum of the first half of the digits is equal to the sum of the second half.

Given a ticket number n, determine if it's lucky or not.

Example:

For n = 1230, the output should be
isLucky(n) = true;
For n = 239017, the output should be
isLucky(n) = false.

Notes: I found that there are always an even number of "bases" in number. We could do the following:

  1. Conver the number into a string
  2. sum the first half, sum the second half
  3. check if equal

I think this could be done more efficently (i.e. casting is expensive) with bit shifting, but i have no clue how.

time complexity: O(N)

Solution:

def sum(a):
    total = 0
    for c in a:
        total += int(c)
    
    return total

def isLucky(number):
    s = str(number)
    n = len(s)
    half = n // 2
    first, second = s[:half], s[half:]
    return sum(first) == sum(second) 

isomorphic array

Two two-dimensional arrays are isomorphic if they have the same number of rows and each pair of respective rows contains the same number of elements.

Given two two-dimensional arrays, check if they are isomorphic.

Example:

[[1, 1, 1], [0, 0]] and [[2, 1, 1], [2, 1]] is true

[[2], []] and [[2]] is false

Notes: So we dont need to check every single item (M*N), we just need to check every row's length As a base case we could confirm that there are the same number of rows. This guarentees a same height, then check each row for the same length

Time complexity: O(N)

Solution:

def areIsomorphic(array1, array2):
    if len(array1) != len(array2):
        return False
    
    for i in range(len(array1)):
        if len(array1[i]) != len(array2[i]):
            return False
        
    return True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment