TheAlgorithms-Python

1
"""
2
Given an array of integers and another integer target,
3
we are required to find a triplet from the array such that it's sum is equal to
4
the target.
5
"""
6

7
from __future__ import annotations
8

9
from itertools import permutations
10
from random import randint
11
from timeit import repeat
12

13

14
def make_dataset() -> tuple[list[int], int]:
15
    arr = [randint(-1000, 1000) for i in range(10)]
16
    r = randint(-5000, 5000)
17
    return (arr, r)
18

19

20
dataset = make_dataset()
21

22

23
def triplet_sum1(arr: list[int], target: int) -> tuple[int, ...]:
24
    """
25
    Returns a triplet in the array with sum equal to target,
26
    else (0, 0, 0).
27
    >>> triplet_sum1([13, 29, 7, 23, 5], 35)
28
    (5, 7, 23)
29
    >>> triplet_sum1([37, 9, 19, 50, 44], 65)
30
    (9, 19, 37)
31
    >>> arr = [6, 47, 27, 1, 15]
32
    >>> target = 11
33
    >>> triplet_sum1(arr, target)
34
    (0, 0, 0)
35
    """
36
    for triplet in permutations(arr, 3):
37
        if sum(triplet) == target:
38
            return tuple(sorted(triplet))
39
    return (0, 0, 0)
40

41

42
def triplet_sum2(arr: list[int], target: int) -> tuple[int, int, int]:
43
    """
44
    Returns a triplet in the array with sum equal to target,
45
    else (0, 0, 0).
46
    >>> triplet_sum2([13, 29, 7, 23, 5], 35)
47
    (5, 7, 23)
48
    >>> triplet_sum2([37, 9, 19, 50, 44], 65)
49
    (9, 19, 37)
50
    >>> arr = [6, 47, 27, 1, 15]
51
    >>> target = 11
52
    >>> triplet_sum2(arr, target)
53
    (0, 0, 0)
54
    """
55
    arr.sort()
56
    n = len(arr)
57
    for i in range(n - 1):
58
        left, right = i + 1, n - 1
59
        while left < right:
60
            if arr[i] + arr[left] + arr[right] == target:
61
                return (arr[i], arr[left], arr[right])
62
            elif arr[i] + arr[left] + arr[right] < target:
63
                left += 1
64
            elif arr[i] + arr[left] + arr[right] > target:
65
                right -= 1
66
    return (0, 0, 0)
67

68

69
def solution_times() -> tuple[float, float]:
70
    setup_code = """
71
from __main__ import dataset, triplet_sum1, triplet_sum2
72
"""
73
    test_code1 = """
74
triplet_sum1(*dataset)
75
"""
76
    test_code2 = """
77
triplet_sum2(*dataset)
78
"""
79
    times1 = repeat(setup=setup_code, stmt=test_code1, repeat=5, number=10000)
80
    times2 = repeat(setup=setup_code, stmt=test_code2, repeat=5, number=10000)
81
    return (min(times1), min(times2))
82

83

84
if __name__ == "__main__":
85
    from doctest import testmod
86

87
    testmod()
88
    times = solution_times()
89
    print(f"The time for naive implementation is {times[0]}.")
90
    print(f"The time for optimized implementation is {times[1]}.")
91