Hacks

import random

def gcd(a, b):
    # base case
    if a == 0:
        return b
    if b == 0:
        return a

    # recursive step
    if a >= b:
        return gcd(a % b, b)
    else:
        return gcd(a, b % a)

num1 = random.randint(0,1000)
num2 = random.randint(0,1000)

print("Numbers being compared:", num1, "&", num2)
print("The greatest common divisor between", num1, "&", num2, "is:")
gcd(num1, num2)

Numbers being compared: 744 & 810
The greatest common divisor between 744 & 810 is:

6
  1. The function starts by defining a base case where gcd(a, b) is equal to a if b is 0, and b if a is 0. This is because the GCD of a number and 0 is always the number itself.
  2. The next step is the recursive step, where the function calls itself with the arguments (a % b, b) if a is greater than or equal to b, or (a, b % a) if b is greater than a. This step is based on the Euclidean algorithm, which states that the GCD of two numbers a and b is the same as the GCD of b and the remainder of a divided by b (i.e. a % b).
  3. This recursive step continues until the base case is reached, at which point the function returns the GCD of a and b.

Binary Search Hacks

def binary_search(array, x):
  low = 0
  high = len(array) - 1
  
  while low <= high:
    mid = low + (high - low) // 2

    if array[mid] == x:
      return mid
    elif array[mid] < x:
      low = mid + 1
    else:
      high = mid - 1

  return -1

array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binary_search(array, x)

if result != -1:
  print("Element is present at index " + str(result))
else:
  print("Element is not present in the array")

Element is present at index 1

This implementation follows the steps outlined in the previous section:

  1. It initializes the low and high pointers to the start and end of the array, respectively.
  2. It uses a while loop to iterate until the low and high pointers meet each other.
  3. In each iteration, it finds the middle element of the current subarray (defined by the low and high pointers) and compares it to the target x.
  4. If the middle element is equal to x, it returns the index of the middle element.
  5. If x is greater than the middle element, it updates the low pointer to be the element immediately after the middle element, so that the search will continue on the right (greater) half of the array.
  6. If x is smaller than the middle element, it updates the high pointer to be the element immediately before the middle element, so that the search will continue on the left (lower) half of the array.
  7. If the while loop completes without finding x, it returns -1 to indicate that x is not present in the array.