LeetCode-Problem-Solving/learing python.py at main · yasir227/LeetCode-Problem-Solving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

income = 50000
tax_payable = 0
#print("Given income", income)

if income <= 10000:
    tax_payable = 0
elif income <= 20000:
    # no tax on first 10,000
    x = income - 10000
    # 10% tax
    tax_payable = x * 10 / 100
else:
    # first 10,000
    tax_payable = 0

    # next 10,000 10% tax
    tax_payable = 10000 * 10 / 100

    # remaining 20%tax
    tax_payable += (income - 20000) * 20 / 100

#print("Total tax to pay is", tax_payable)

############# 00101010101

#print("Hello World!!")


######## Binary search problem #####

def binary_search(alist, key):
    if len(alist) > 0:
        mid = len(alist) // 2

        if alist[mid] == key:
            return True

        elif alist[mid] > key:
            return binary_search(alist[:mid], key)

        elif alist[mid] < key:
            return binary_search(alist[mid+1:], key)

    else:
        return False


#print(binary_search([10, 20, 30, 40], 20))
#print(binary_search([10, 20, 30, 40], 40))
#print(binary_search([1, 1, 3, 4, 11, 33, 44, 55], 10))

########## Greedy Algorithm in python #################

def activity_selection(activities):
    # Step 1: Sort activities by finish time
    activities.sort(key=lambda x: x[1])  # Sort by end time

    selected_activities = []  # Store selected activities
    last_end_time = 0  # Track last selected activity's end time

    # Step 2: Iterate over activities
    for start, end in activities:
        if start >= last_end_time:  # Step 3: Select if non-overlapping
            selected_activities.append((start, end))
            last_end_time = end  # Update last selected end time

    return selected_activities  # Return the list of selected activities

# Example usage
activities = [(1, 3), (2, 5), (3, 9), (6, 8), (5, 7), (8, 9)]
selected = activity_selection(activities)

print("Selected Activities:", selected)


########### Array

def find_subarray_with_target_sum(arr, target):
    # Iterate through the array to find the subarray that sums up to the target
    for start in range(len(arr)):
        current_sum = 0
       # print(start)
        for end in range(start, len(arr)):
            #print (len(arr))
            current_sum += arr[end]
            if current_sum == target:
                return [start, end]
    return None  # If no such subarray is found

# Example usage
arr = [1, 2, 3, 7, 5]
target = 12
result = find_subarray_with_target_sum(arr, target)

if result:
    print(f"Output: {result}")
else:
    print("No subarray with the given target sum found.")