Advertisement
makispaiktis

Egyptian Fractions

Apr 27th, 2021 (edited)
847
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.39 KB | None | 0 0
  1. '''
  2. Good morning! Here's your coding interview problem for today.
  3. This problem was asked by Palantir.
  4. The ancient Egyptians used to express fractions as a sum of several terms where each numerator is one.
  5. For example, 4 / 13 can be represented as 1 / 4 + 1 / 18 + 1 / 468.
  6. Create an algorithm to turn an ordinary fraction a / b, where a < b, into an Egyptian fraction.
  7. '''
  8. import random
  9.  
  10. # FUNCTION 1
  11. def egyptian(a, b):
  12.     if a != int(a) or b != int(b) or a <= 0 or b <= 0 or a >= b:
  13.         print("Error while using function " + egyptian.__name__)
  14.     # Now, I will begin the scanning
  15.     SUM = 0
  16.     target = a / b
  17.     counter = 2
  18.     LIMIT = 10 ** 5
  19.     numbers = list()
  20.     while SUM < target and counter <= LIMIT:
  21.         if target - SUM >= 1 / counter:
  22.             SUM += 1 / counter
  23.             numbers.append(counter)
  24.         counter += 1
  25.     return numbers
  26.  
  27.  
  28. # FUNCTION 2
  29. def prettyPrint(a, b):
  30.     numbers = egyptian(a, b)
  31.     result = ""
  32.     for i in range(len(numbers)):
  33.         if i != len(numbers) - 1:
  34.             result += "1/" + str(numbers[i]) + " + "
  35.         else:
  36.             result += "1/" + str(numbers[i])
  37.     print(str(a) + "/" + str(b) + " = " + result)
  38.  
  39. # MAIN FUNCTION
  40. prettyPrint(7, 12)
  41. prettyPrint(1, 12)
  42. prettyPrint(5, 6)
  43. prettyPrint(2, 3)
  44. prettyPrint(4, 13)
  45. prettyPrint(3, 10)
  46. prettyPrint(random.randrange(2, 10), random.randrange(11, 20))
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement