import numpy as np
import math
s = [1,2,3,5,10, 15, 20]
#print("Set", s)
n= int(math.pow(2,len(s)))
#print(power, n)
A = np.zeros(n)
C1 = []
for item in s:
A[item] = 1
A1 = np.fft.fft(A)
# print(len(A1), type(A1), A1)
for i in range(0,n,1):
C1.append(A1[i]*A1[i]*A1[i])
C = np.fft.ifft(C1)
#print(C, C[19].real)
for i in range(0,n,1):
if C[i].real>=.999999:
print(i,"yes")
else:
print(i,"no")
# Driver Code
A = [6, 1, 12]
B = [1, 0, 8]
C = [0,0,0]
prev = 0
for i in range(0, len(A)):
prev = 0
#print("iteration I=", i)
for j in range (0, len(B)):
#print("iteration J=", j)
temp = abs(A[i]-B[j])
#print("Temp", A[i], B[j], temp, prev)
if(temp >= 0):
if(j == 0):
prev= temp
C[i] = B[j]
if(A[i] == B[j]):
prev = temp
C[i] = B[j]
#print("if", temp, prev)
elif (temp < prev):
prev = temp
C[i]= B[j]
#print("elif", C[i], prev)
print(C)
Output is: C = [8, 1, 8]
Time Complexity is O(Log n) . Its better and faster without recursion.
from random import randint
import math
random_odd_numbers = list((val
for val in iter(lambda: randint(-64, 64), 0) if val % 2 != 0))
mylist = sorted(set(random_odd_numbers))
l = 0
h = len(mylist)
while ((h - l) > 1):
mid = math.ceil((l + h) / 2)
#print(mylist[mid], l, mid, h - 1)
if mylist[mid] == 2 * mid + 5 or(mylist[h - 1] == 2 * h + 5) or mylist[l] == 2 * l + 5:
print(2 * h + 5, "yes", mylist)
break
elif mylist[mid] < 2 * mid + 5:
l = mid
else :
h = mid
Time Complexity O(n log n)
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):
# Check base case
#print(x, r)
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return True
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return False
# Driver Code
arr = [ 2, 4, 8, -9, 14, 20, 69 ]
for x in (2**p for p in range(1, len(arr))):
#print(2*x+5)
result = binarySearch(arr, 0, len(arr)-1, (2*x+5))
if(result == True):
print (2*x+5, " - Element is present in the array")
break
if(result == False):
print ("Element is not present in array")
# Function call
Dynamic programming exercise to count number of ways to reach n steps using either n+1 or n+4 steps. Had to use count global variable, as returning r was not giving me the correct answer. This works as expected.
Recursive algorithm - solve(n - 1) + solve(n - 4)
Python code sample:
count = 0
def solve(n):
global count
# Base case
if n < 0:
return 0
if n == 0:
return 1
if n == 1:
count = count + 1
return 1
r = solve(n - 1) + solve(n - 4)
return r
# Driver program to test above function
n = 6
ret = solve(n)
print("Final:", count)
Output of this program is 3.
Example: for n = 6 there are 3 ways to get from stairs 1 to stairs 6.
Those are:
1 → 2 → 3 → 4 → 5 → 6,
1 → 2 → 6, and
1 → 5 → 6