Singleton Finder

Given a sorted array in which each element appears twice and only one element appears once. find that element.

# Time: O (log n)
#
# Input: [1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8]
# output: 4
#
def FindSingleton(A, l, r) :
    if l > r:
        return

    if l == r:
        return A[l]

    # Find middle point 
    m = (l + r) // 2

    if (m % 2) == 0:
        if A[m] == A[m + 1]:
            return FindSingleton(A, m + 2, r)
        else:
            return FindSingleton(A, l, m)
    else:
        if A[m] == A[m - 1]:
            return FindSingleton(A, m + 1, r)
        else:
            return FindSingleton(A, l, m - 1)

Find an Extra Element

Given two arrays A and B of integers. The arrays are identical except that B has an extra element inserted at some index. (Thus |A|+ 1 = |B|.) Find the inserted value.

For example, if a = [1, 5, 2] and b = [1, 4, 5, 2] then a 4 was inserted.

A divide-and-conquer algorithm to find the extra element with complexity of O (log |A|):

# Time: O (log A)
#
def FindExtra(A, B, l, r):
    # only 1 element
    if (l == r) :
        if(A[l] == B[l]):
            return B[r+1]
        else:
            return B[r]
    

    # Find middle point 
    m = (l + r) // 2

    if(A[m] == B[m]):
        # go right
        return FindExtra(A, B, m+1, r)
    else:
        # (A[m] == B[m+1])
        # target on the left, go left
        return FindExtra(A, B, l, m)

Find Power Set

Given a set of characters, find the power set.

A power set should have  sets where n is number of elements in the original set.

For example, the power set of {1, 2, 3} is {, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, which has 9 sets inside.

Since there are  sets of elements, we need to loop at least  time, an algorithm using mechanism of binary number to filter out every subset can be done:

# Time: O (2^n x n)
#
def subsets(a_set):
    length = len(a_set)

    # number of subset is 2^length
    # so 1 << length
    # 1 << 2 = 100 = 4
    for i in range(0, (1 << length)):
        subset = set()
        for j in range(0, length):
            # 1010
            # take 2nd, and 4th
            # so 1 << 1 = 0010, and 1 << 3 = 1000
            index = (i & (1 << j)) if(index > 0):
                subset.add(a_set[j])
        print(subset)


# Test:
subsets((1,2,3,4))

Print All Valid parenthesises

Print all valid parenthesis combinations given a number of set of parenthesis.

All parenthesis combination should be valid which means they can be applied to valid math calculation.

For example, combinations of 2 pair of parenthesis:
( )( )
( ( ) )

def printParenthesis(n):
    # Embeded recursive fnc
    def parenthesis(str, pos, n, open, close): 
        
        if(close == n): 
            for i in str: 
                print(i, end = "")
            print()
            return
        else: 
            if(open > close): 
                str[pos] = ' )'
                parenthesis(str, pos + 1, n,  
                                open, close + 1)
            if(open < n): 
                str[pos] = '( ' 
                parenthesis(str, pos + 1, n, open + 1, close)
    
    # Begin here:
    if(n > 0):
        str = [''] * 2 * n
        parenthesis(str, 0, n, 0, 0)


# Test:
printParenthesis( 3 )
print()
printParenthesis( 4 )