arrays_practice_problems.ipynb 6.0 KB

# Practice Problems
### Problem 1: Given an integer array, find the missing number: - Input = [1, 2, 3, 4, 6, 7] - Output = 5
def missingNumber(arr): 
    n = len(arr) + 1 #Since a number is missing, we need to add an extra element.
    theoritical_sum = (n * (n + 1))/2
    actual_sum = sum(arr)
    return int(theoritical_sum - actual_sum)

missingNumber([1, 2, 3, 4, 6, 7])
5
### Problem 2: Given an integer array, find the pairs whose sum is equal to a given number. - Input: [1, 2, 3, 4, 5] target_sum = 7 - Output: (3, 4), (2, 5)
# Method 1
def findSum(arr, target): # Time Complexity: O(n^2)
    results = []
    for i in arr:
        for j in arr:
            if i == j:
                continue
            if (i + j) == target:
                results.append(tuple([i, j]))
    
    return list(set(results))

findSum([1, 2, 3, 4, 5], 7)
[(5, 2), (2, 5), (3, 4), (4, 3)]
# Method 2
def findSum(arr, target): # Time Complexity: O(log(n) + n) => O(n)
    arr.sort()
    results = []
    low = 0 
    high = len(arr) - 1
    while (low < high):
        if (arr[low] + arr[high]) == target:
            results.append(tuple([arr[low], arr[high]]))
        
        if (arr[low] + arr[high]) < target:
            low += 1

        else:
            high -= 1
    return results
findSum([2, 1, 3, 4, 5], 7)
[(2, 5), (3, 4)]
### Problem 3 Given an integer array of range in with length (n + 1), find the duplicate number. - Input: [1, 2, 3, 4, 5, 5, 6] - Output: 5
# Method 1
def findDuplicate(arr): # Time complexity: O(n), Space complexity: O(n)
    data = {}
    for element in arr:
        if element not in data:
            data[element] = 0
        data[element] += 1

    for key, value in data.items():
        if value > 1:
            return key

findDuplicate([1, 2, 3, 4, 5, 5, 6])
5
# Method 2
def findDuplicate(arr): # Time complexity: O(n), Space complexity: O(n)
    data = []
    for element in arr:
        if element in data:
            return element
        else:
            data.append(element)

findDuplicate([1, 2, 3, 4, 5, 5, 6])
5
### Problem 4 Given two lists, check whether the lists are a permutation of each other. Note, you must not use the `.sort()` function. - Input_1: [1, 2, 3, 4], [4, 3, 1, 2] - Output_1: True - Input_2: ["a", "c", "b"], ["j", "c", "b"] - Output_2: False
def isPermutation(list_1, list_2):
    if len(list_1) != len(list_2):
        return False

    count = len([element for element in list_1 if element in list_2])
    if count == len(list_1):
        return True
    else:
        return False
print(isPermutation([1, 2, 3, 4], [4, 3, 1, 2]))
print(isPermutation(["a", "c", "b"], ["j", "c", "b"]))
True
False