Solution 1 - Brute Force

Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Brute Force Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brute Force using `enumerate()`

Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...)).

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Using Enumerate """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for key1, num1 in enumerate(nums):
            for key2, num2 in enumerate(nums[key1 + 1 :], key1 + 1):
	              # enumerate(iterable, start=1) -> start value determines starting index
                # Printing value and key will output 1 i , 2 j, 3 k, 4 l 
                if num1 + num2 == target:
                    return [key1, key2]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 1 - Brute Force

Find the minimum and maximum of the array, then iterate from the smaller value down to 1 checking if both are divisible. Return the first (largest) divisor found.

TimeComplexity: O(n + min(nums))

SpaceComplexity: O(1)

""" 1979.1 - Find Greatest Common Divisor of Array - Solution 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findGCD(self, nums: List[int]) -> int:
        """Find GCD of min and max in array"""
        smallest = min(nums)
        largest = max(nums)
        for i in range(smallest, 0, -1):
            if smallest % i == 0 and largest % i == 0:
                return i


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findGCD([2, 5, 6, 9, 10]))  # 2
    print(Solution().findGCD([7, 5, 6, 8, 3]))    # 1
    print(Solution().findGCD([3, 3]))              # 3


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Euclidean Algorithm

Use the classic Euclidean algorithm to compute the GCD of the minimum and maximum values. Repeatedly replace the larger number with the remainder of dividing the two until the remainder is zero.

TimeComplexity: O(n + log(min(a,b)))

SpaceComplexity: O(1)

""" 1979.2 - Find Greatest Common Divisor of Array - Solution 2 - Euclidean Algorithm """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findGCD(self, nums: List[int]) -> int:
        """Find GCD of min and max in array using Euclidean algorithm"""
        a = min(nums)
        b = max(nums)
        while a:
            a, b = b % a, a
        return b


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findGCD([2, 5, 6, 9, 10]))  # 2
    print(Solution().findGCD([7, 5, 6, 8, 3]))    # 1
    print(Solution().findGCD([3, 3]))              # 3


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Using Python `math.gcd`

Leverage Python's built-in math.gcd function for the most concise and readable solution. Simply pass the minimum and maximum of the array directly.

TimeComplexity: O(n + log(min(a,b)))

SpaceComplexity: O(1)

""" 1979.3 - Find Greatest Common Divisor of Array - Solution 3 - Using math.gcd """

#####################################################################################
# Imports
#####################################################################################
from typing import List
from math import gcd

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findGCD(self, nums: List[int]) -> int:
        """Find GCD of min and max in array using math.gcd"""
        return gcd(min(nums), max(nums))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findGCD([2, 5, 6, 9, 10]))  # 2
    print(Solution().findGCD([7, 5, 6, 8, 3]))    # 1
    print(Solution().findGCD([3, 3]))              # 3


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

1979 - Find Greatest Common Divisor of Array

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Brute Force

Solution 2 - Euclidean Algorithm

Solution 3 - Using Python math.gcd

Solution 2 - Brute Force using `enumerate()`

Solution 3 - Using Python `math.gcd`