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 - Mathematical (Modulo 4)

You are playing the Nim Game with your friend. There is a heap of stones on the table, and you take turns removing 1 to 3 stones. The one who removes the last stone wins. Given n, the number of stones, return True if you can win the game assuming both players play optimally.

The key insight is that if n is divisible by 4, the first player always loses. No matter how many stones (1, 2, or 3) the first player takes, the second player can always take enough to make the total removal 4. Eventually the second player takes the last stone. If n is not divisible by 4, the first player can always reduce it to a multiple of 4 for the opponent, guaranteeing a win.

TimeComplexity: O(1)

SpaceComplexity: O(1)

""" 0292.1 - Nim Game - Solution 1 - Mathematical (Modulo 4) """

#####################################################################################
# Imports
#####################################################################################


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

    def canWinNim(self, n: int) -> bool:
        """Nim Game Function"""
        return n % 4 != 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().canWinNim(4))    # False
    print(Solution().canWinNim(1))    # True
    print(Solution().canWinNim(2))    # True
    print(Solution().canWinNim(3))    # True
    print(Solution().canWinNim(5))    # True
    print(Solution().canWinNim(8))    # False


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

Solution 2 - Bitwise AND

Same mathematical principle, but uses bitwise AND instead of the modulo operator. Since 4 is a power of 2, checking n % 4 != 0 is equivalent to checking n & 3 != 0. The two least-significant bits determine the remainder when dividing by 4.

TimeComplexity: O(1)

SpaceComplexity: O(1)

""" 0292.2 - Nim Game - Solution 2 - Bitwise AND """

#####################################################################################
# Imports
#####################################################################################


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

    def canWinNim(self, n: int) -> bool:
        """Nim Game Function"""
        return (n & 3) != 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().canWinNim(4))    # False
    print(Solution().canWinNim(1))    # True
    print(Solution().canWinNim(2))    # True
    print(Solution().canWinNim(3))    # True
    print(Solution().canWinNim(5))    # True
    print(Solution().canWinNim(8))    # False


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

0292 - Nim Game

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Mathematical (Modulo 4)

Solution 2 - Bitwise AND

Solution 2 - Brute Force using `enumerate()`