Added new solutions

Мето Трајковски · Мето Трајковски · commit 4f77335b5387 · 2019-12-09T14:40:02.000+01:00
diff --git a/Lists/find_el_where_k_greater_or_equal.py b/Lists/find_el_where_k_greater_or_equal.py
@@ -0,0 +1,49 @@
+'''
+Find an Element Which is Smaller or Equal to Exactly K Numbers
+
+You have to find some number X greater than 0 where exactly K elements in that list are greater than or equal to the number X.
+If there are multiple such values return the smallest possible.
+If there is no such X, return (-1).
+
+Input: [3,8,5,1,10,3,20,24], 2
+Output: 11
+Output explanation: Only 20 and 24 are greater or smaller from 11 (11 is the smallest solution, also 12, 13...20 are solutions).
+
+=========================================
+Sort the array and check the Kth element from the end.
+    Time Complexity:    O(NLogN)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def get_minimum_X(arr, k):
+    n = len(arr)
+
+    if n == 0 or k > n:
+        return -1
+
+    if k == n:
+        return 1
+
+    arr.sort()
+
+    if k == 0:
+        return arr[-1] + 1
+
+    if arr[-k] == arr[-(k + 1)]:
+        return -1
+
+    return arr[-(k + 1)] + 1
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => 11
+print(get_minimum_X([3, 8, 5, 1, 10, 3, 20, 24], 2))
diff --git a/Math/odd_sum.py b/Math/odd_sum.py
@@ -0,0 +1,48 @@
+'''
+Odd Sum
+
+For a given range [а,b], find the sum of all odd numbers between a and b.
+
+Input: 3, 9
+Output: 24
+Output explanation: 3+5+7+9=24
+
+=========================================
+Several different O(1) approaches exist. This is the explanation of my solution/formula.
+3 + 5 + 7 + 9 can be written like (3 + 0) + (3 + 2) + (3 + 4) + (3 + 6)
+that's (3 * 4) + (2 + 4 + 6), also this can be written like
+(3 * 4) + ((2 * 1) + (2 * 2) + (2 * 3)) = 3 * 4 + 2 * (1 + 2 + 3)
+And the formula is: Min_Odd * Num_Odds + 2 * Sum(Num_Odds)
+Sum formula is N*(N-1)/2. (for all numbers smaller than N)
+This is the simplest formula:
+Min_Odd * Num_Odds + 2 * Num_Odds * (Num_Odds - 1) / 2 =
+Num_Odds * (Min_Odd + Num_Odds - 1)
+    Time Complexity:    O(1)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def odd_sum(a, b):
+    # find first odd number
+    if a % 2 == 0:
+        a += 1
+    # to avoid rounding (math.ceil) find the biggest even number
+    if b % 2 == 1:
+        b += 1
+    # count of odd numbers
+    n = (b - a + 1) // 2
+    # use the formula from the description
+    return n * (a + n - 1)
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => 24
+print(odd_sum(3, 9))
diff --git a/Math/total_divisible_numbers.py b/Math/total_divisible_numbers.py
@@ -0,0 +1,52 @@
+'''
+Total Divisible Numbers
+
+Given an array A of N numbers,
+your task is to find how many numbers from 1 to S are divisible by all of the elements in the array.
+
+Input: [2, 4, 5], 45
+Output: 2
+Output explanation: 20 and 40 are divisible by all numbers in the array.
+
+=========================================
+Find least common multiple of all numbers in the array (lcm can be found using gcd, (a * b)/gcd(a, b)).
+And in the end check how many numbers are divisble by the lcm number (smaller or equal to S).
+    Time Complexity:    O(N)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def total_divisible_numbers(arr, S):
+    # find lcm for all numbers in the array
+    lcm = 1
+    for a in arr:
+        lcm = (a * lcm) // gcd(a, lcm)
+
+    # return the count of numbers divisble by the lcm number (smaller or equal to S)
+    return S // lcm
+
+def gcd(a, b):
+    while a != 0:
+        a, b = b % a, a
+    return b
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => 4
+print(total_divisible_numbers([3, 5, 6], 146))
+
+# Test 2
+# Correct result => 52
+print(total_divisible_numbers([3, 3, 2], 317))
+
+# Test 3
+# Correct result => 30
+print(total_divisible_numbers([2, 3], 30))
