#Using binary search
#Search the number of negative numbers in grid
grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
def binary_search(row):
left = 0
right = len(row)
while left < right:
mid = (left + right) // 2
if row[mid] < 0:
right = mid
else:
left = mid + 1
return len(row) - right
s = 0
for i in grid:
s += (binary_search(i))
print(s)
8
"""
You are given an array nums of non-negative integers. nums is considered special
if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.
"""
nums = [0,4,3,0,4]
nums.sort()
print(nums)
def count(arr,n):
c = 0
for i in arr:
if i >= n:
c +=1
return c
def binary_search(arr):
left = 1
right = len(arr)
while left <= right:
mid = (left + right) // 2
counting = count(arr,mid)
if counting > mid:
left = mid + 1
elif counting < mid:
right = mid - 1
else:
return mid
return -1
print(binary_search(nums))
[0, 0, 3, 4, 4]
3
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
class TREE:
def __init__(self):
self.root = None
def addNode(self,node,data):
if self.root is None:
self.root = Node(data)
return
else:
if node.data > data:
if node.left is None:
node.left = Node(data)
else:
self.addNode(node.left,data)
else:
if node.right is None:
node.right = Node(data)
else:
self.addNode(node.right,data)
def inorder(self,node):
if node is None:
return
if node.left:
self.inorder(node.left)
print(node.data, end = " ")
if node.right:
self.inorder(node.right)
def DFS(self,node):
stack = []
curr = node
total = 0
while True:
if curr != None:
stack.append(curr)
curr = curr.right
elif stack:
curr = stack.pop()
total += curr.data
curr.data = total
curr = curr.left
else:
break
return node
tree = TREE()
a = [4,1,6,0,2,5,7,3,8]
for i in a:
tree.addNode(tree.root,i)
tree.inorder(tree.root)
print()
tree.DFS(tree.root)
tree.inorder(tree.root)
0 1 2 3 4 5 6 7 8
36 36 35 33 30 26 21 15 8