getminSum.py
· 1.1 KiB · Python
Eredeti
def getMinimumSum(arr):
n = len(arr)
if n < 3:
return -1
left_min = [None] * n
min_so_far = float('inf')
# Populate left_min
for j in range(n):
if min_so_far < arr[j]:
left_min[j] = min_so_far
else:
left_min[j] = None
if arr[j] < min_so_far:
min_so_far = arr[j]
right_min = [None] * n
min_so_far = float('inf')
# Populate right_min
for j in range(n-1, -1, -1):
if min_so_far < arr[j]:
right_min[j] = min_so_far
else:
right_min[j] = None
if arr[j] < min_so_far:
min_so_far = arr[j]
min_sum = float('inf')
for j in range(n):
if left_min[j] is not None and right_min[j] is not None:
current_sum = left_min[j] + arr[j] + right_min[j]
if current_sum < min_sum:
min_sum = current_sum
return min_sum if min_sum != float('inf') else -1
# Example Usage:
if __name__ == "__main__":
arr = [3, 4, 5, 1, 2, 3, 1]
result = getMinimumSum(arr)
print(result) # Output: 4
| 1 | |
| 2 | def getMinimumSum(arr): |
| 3 | n = len(arr) |
| 4 | if n < 3: |
| 5 | return -1 |
| 6 | |
| 7 | left_min = [None] * n |
| 8 | min_so_far = float('inf') |
| 9 | |
| 10 | # Populate left_min |
| 11 | for j in range(n): |
| 12 | if min_so_far < arr[j]: |
| 13 | left_min[j] = min_so_far |
| 14 | else: |
| 15 | left_min[j] = None |
| 16 | if arr[j] < min_so_far: |
| 17 | min_so_far = arr[j] |
| 18 | |
| 19 | right_min = [None] * n |
| 20 | min_so_far = float('inf') |
| 21 | |
| 22 | # Populate right_min |
| 23 | for j in range(n-1, -1, -1): |
| 24 | if min_so_far < arr[j]: |
| 25 | right_min[j] = min_so_far |
| 26 | else: |
| 27 | right_min[j] = None |
| 28 | if arr[j] < min_so_far: |
| 29 | min_so_far = arr[j] |
| 30 | |
| 31 | min_sum = float('inf') |
| 32 | for j in range(n): |
| 33 | if left_min[j] is not None and right_min[j] is not None: |
| 34 | current_sum = left_min[j] + arr[j] + right_min[j] |
| 35 | if current_sum < min_sum: |
| 36 | min_sum = current_sum |
| 37 | |
| 38 | return min_sum if min_sum != float('inf') else -1 |
| 39 | |
| 40 | # Example Usage: |
| 41 | if __name__ == "__main__": |
| 42 | arr = [3, 4, 5, 1, 2, 3, 1] |
| 43 | result = getMinimumSum(arr) |
| 44 | print(result) # Output: 4 |
| 45 | |
| 46 |
sumof_factors.py
· 511 B · Python
Eredeti
def sum_of_factors(num):
# Sum of factors of num
sum_factors = 0
for i in range(1, int(num**0.5) + 1):
if num % i == 0:
sum_factors += i
if i != num // i:
sum_factors += num // i
return sum_factors
def maxSubsetSum(arr):
# Apply sum_of_factors to each element in arr
return [sum_of_factors(num) for num in arr]
# Example usage:
arr = [12] # Example input from the image
result = maxSubsetSum(arr)
print(result) # Expected output: [28]
| 1 | def sum_of_factors(num): |
| 2 | # Sum of factors of num |
| 3 | sum_factors = 0 |
| 4 | for i in range(1, int(num**0.5) + 1): |
| 5 | if num % i == 0: |
| 6 | sum_factors += i |
| 7 | if i != num // i: |
| 8 | sum_factors += num // i |
| 9 | return sum_factors |
| 10 | |
| 11 | def maxSubsetSum(arr): |
| 12 | # Apply sum_of_factors to each element in arr |
| 13 | return [sum_of_factors(num) for num in arr] |
| 14 | |
| 15 | # Example usage: |
| 16 | arr = [12] # Example input from the image |
| 17 | result = maxSubsetSum(arr) |
| 18 | print(result) # Expected output: [28] |
| 19 |