DICTIONARY: Return min_val
find non-paired/ odd number of element(s):
Pairs = {}
Frog earliest jump
For ele in arr:
#try using enumerate to limit for loops
If ele in, increase
Jumps = set()
Else set ele to 1
To_jump = set(range(1, X + 1))
Keys = list(pairs.keys())
For I, leaf in enumerate(A):
Vals = list(pairs.values())
Jumps.add(leaf)
Single = vals.index(1)
If jumps == to_jump:
Ind = [x for x in vals if x % 2 != 0]
Return i
Odd = vals.index(ind[0])
Return -1
Return keys[odd]
Efficient algorithm Passing cars
minimum frog jump def solution(A):
Import math zeros = 0
Return math.ceil((Y-X)/D) passing = 0
for i in A:
Missing element in array if i == 0:
S = set(A) zeros += 1
Count = 1 else:
While count in S: passing += zeros
count += 1
return passing
Return count
range divisible by K
Absolute difference between sum of parts
#reduce sum as much as possible via adding as you div = [I for I in range(A, B+1) if i%K == 0]
go
return len(div)
#write out all steps to see how to simplify
#think of how many values are used in example
Living fish moving in opposite
Start = A[0] directions
End = sum(A[1:])
Ind = 0
Min_val = abs(start – end)
Fish = 0
For x in range(1, len(A) - 1):
If len(A) == 1:
Start += A[x]
Return 1
End -= A[x]
For x in range(len(A) – 1):
If abs(start – end) < min_val:
If B[ind] != B[ind + 1]:
Min_val = abs(start – end)
If (A[ind] > B[ind]) or (B[ind] >
A[ind]):
Fish += 1
Ind += 1
Return fish
Dominator
from collections import Counter
Minimum sum of largest sum array:
def solution(A):
# Implement your solution here
def solution(K, M, A):
pass
# Implement your solution here
most = Counter(A).most_common(1)[0]
# NOTES:
if most and most[1] > len(A) // 2:
# large sum: block with most elements
return A.index(most[0])
return -1
left = 0
right = len(A)
max sum of sub array
large_sum = sum(A)
def solution(A):
if len(A) <= 2 and K <= 2:
# Implement your solution here
return max(A)
pass
while len(A[left:right]) > K :
max_sum = A[0]
if sum(A[left + 1:right]) < large_sum:
ind = 0
left += 1
for i in range(1, len(A) - 2):
large_sum = sum(A[left:right])
if A[ind] + A[i] > max_sum:
max_sum += A[i]
elif sum(A[left:right - 1]) < large_sum:
right -= 1
return max_sum
large_sum = sum(A[left:right])
#print(A[left:right])
return large_sum
Data Structures
Generic Binary Search
Here is the general strategy behind binary search, which is applicable to a variety of problems:
1. Come up with a condition to determine whether the answer lies before, after or at a given
position
2. Retrieve the midpoint and the middle element of the list.
3. If it is the answer, return the middle position as the answer.
4. If answer lies before it, repeat the search with the first half of the list
5. If the answer lies after it, repeat the search with the second half of the list.
Here is the generic algorithm for binary search, implemented in Python:
def binary_search(lo, hi, condition):
"""TODO - add docs"""
while lo <= hi:
mid = (lo + hi) // 2
result = condition(mid)
if result == 'found':
return mid
elif result == 'left':
hi = mid - 1
else:
lo = mid + 1
return -1
The worst-case complexity or running time of binary search is O(log N), provided the complexity of
the condition used to determine whether the answer lies before, after or at a given position is O(1).
Note that binary_search accepts a function condition as an argument. Python allows passing
functions as arguments to other functions, unlike C++ and Java.
We can now rewrite the locate_card function more succinctly using the binary_search function.
def locate_card(cards, query):
def condition(mid):
if cards[mid] == query:
if mid > 0 and cards[mid-1] == query:
return 'left'
else:
return 'found'
elif cards[mid] < query:
return 'left'
else:
return 'right'
return binary_search(0, len(cards) - 1, condition)
The __str__() and __repr__() methods return the object's string
representation. The __repr__() representation is intended to hold
information about the object so that it may be created again. In
contrast, the __str__() string representation is human-friendly and
mainly used for logging reasons.
Passing cars
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# Implement your solution here
pass
# count cars going west
west_count = sum(A)
for i in range(len(A)):
# if a car shows up going east, add it to the count
if A[i] == 0:
west_count += 1
if west_count > 1_000_000_000:
return -1
return west_count
