Showing posts with label Functions. Show all posts
Showing posts with label Functions. Show all posts

Sorted Linked List to Balanced Binary search tree

class LNode :

def __init__(self):

self.data = None

self.next = None

class TNode :

def __init__(self):

self.data = None

self.left = None

self.right = None

head = None

def sortedListToBST():

global head

n = countLNodes(head)

return sortedListToBSTRecur(n)

def sortedListToBSTRecur( n) :

global head

if (n <= 0) :

return None

left = sortedListToBSTRecur( int(n/2))

root = newNode((head).data)

root.left = left

head = (head).next

root.right = sortedListToBSTRecur( n - int(n/2) - 1)

return root

def countLNodes(head) :

count = 0

temp = head

while(temp != None):

temp = temp.next

count = count + 1

return count

def push(head, new_data) :

new_node = LNode()

new_node.data = new_data

new_node.next = (head)

(head) = new_node

return head

def printList(node):

while(node != None):

print( node.data ,end= " ")

node = node.next

def newNode(data) :

node = TNode()

node.data = data

node.left = None

node.right = None

return node

def preOrder( node) :

if (node == None) :

return

print(node.data, end = " " )

preOrder(node.left)

preOrder(node.right)

head = None

head = push(head, 7)

head = push(head, 6)

head = push(head, 5)

head = push(head, 4)

head = push(head, 3)

head = push(head, 2)

head = push(head, 1)

print("Given Linked List " )

printList(head)

root = sortedListToBST()

print("\nPreOrder Traversal of constructed BST ")

preOrder(root)

Moser-de Bruijn Sequence

def gen(n):

if n == 0:

return 0

elif n ==1:

return 1

elif n % 2 ==0:

return 4 * gen(n // 2)

elif n % 2 == 1:

return 4 * gen(n // 2) +1

def moserDeBruijn(n):

for i in range(n):

print(gen(i), end = " ")

n = 15

print("First", n, "terms of ",

"Moser-de Bruijn Sequence:")

moserDeBruijn(n)


Interpolation Search

def interpolationSearch(arr, lo, hi, x):

if (lo <= hi and x >= arr[lo] and x <= arr[hi]):

pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) *

(x - arr[lo]))

if arr[pos] == x:

return pos

if arr[pos] < x:

return interpolationSearch(arr, pos + 1,

hi, x)

if arr[pos] > x:

return interpolationSearch(arr, lo,

pos - 1, x)

return -1

arr = [10, 12, 13, 16, 18, 19, 20,

21, 22, 23, 24, 33, 35, 42, 47]

n = len(arr)

x = 18

index = interpolationSearch(arr, 0, n - 1, x)

if index != -1:

print("Element found at index", index)

else:

print("Element not found")


program to add two numbers in base 14

def getNumeralValue(num) :

if( num >= '0' and num <= '9') :

return ord(num) - ord('0')

if( num >= 'A' and num <= 'D') :

return ord(num ) - ord('A') + 10

def getNumeral(val):

if( val >= 0 and val <= 9):

return chr(val + ord('0'))

if( val >= 10 and val <= 14) :

return chr(val + ord('A') - 10)

def sumBase14(num1, num2):

l1 = len(num1)

l2 = len(num2)

carry = 0

if(l1 != l2) :

print("Function doesn't support numbers of different"

" lengths. If you want to add such numbers then"

" prefix smaller number with required no. of zeroes")

res = [0]*(l1 + 1)

for i in range(l1 - 1, -1, -1):

nml1 = getNumeralValue(num1[i])

nml2 = getNumeralValue(num2[i])

res_nml = carry + nml1 + nml2;

if(res_nml >= 14) :

carry = 1

res_nml -= 14

else:

carry = 0

res[i+1] = getNumeral(res_nml)

if(carry == 0):

return (res + 1)

res[0] = '1'

return res

if __name__ == "__main__":

num1 = "DC2"

num2 = "0A3"

print("Result is ",end="")

res = sumBase14(num1, num2)

for i in range(len(res)):

print(res[i],end="")


checking the given number is Lucky or Not

import math

def isLucky(n):

ar = [0] * 10

while (n > 0):

digit = math.floor(n % 10)

if (ar[digit]):

return 0

ar[digit] = 1

n = n / 10

return 1

arr = [1291, 897, 4566, 1232, 80, 700]

n = len(arr)

for i in range(0, n):

k = arr[i]

if(isLucky(k)):

print(k, " is Lucky ")

else:

print(k, " is not Lucky ")


Maximum profit by buying and selling a share at most k times

def maxProfit(prices, n, k):

profit = [[0 for i in range(k + 1)]

for j in range(n)]

for i in range(1, n):

for j in range(1, k + 1):

max_so_far = 0

for l in range(i):

max_so_far = max(max_so_far, prices[i] -

prices[l] + profit[l][j - 1])

profit[i][j] = max(profit[i - 1][j], max_so_far)

return profit[n - 1][k]

k = 2

prices = [10, 22, 5, 75, 65, 80]

n = len(prices)

print("Maximum profit is:",

maxProfit(prices, n, k))


Program to generate CAPTCHA and verify user

import random

def checkCaptcha(captcha, user_captcha):

if captcha == user_captcha:

return True

return False

def generateCaptcha(n):

chrs = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

captcha = ""

while (n):

captcha += chrs[random.randint(1, 1000) % 62]

n -= 1

return captcha

captcha = generateCaptcha(9)

print(captcha)

print("Enter above CAPTCHA:")

usr_captcha = input()

if (checkCaptcha(captcha, usr_captcha)):

print("CAPTCHA Matched")

else:

print("CAPTCHA Not Matched")


Program for Extended Euclidean algorithms

def gcdExtended(a, b):

if a == 0 :

return b,0,1

gcd,x1,y1 = gcdExtended(b%a, a)

x = y1 - (b//a) * x1

y = x1

return gcd,x,y

a, b = 35,15

g, x, y = gcdExtended(a, b)

print("gcd(", a , "," , b, ") = ", g)


program to print all Prime numbers in an Interval

def prime(x, y):

prime_list = []

for i in range(x, y):

if i == 0 or i == 1:

continue

else:

for j in range(2, int(i/2)+1):

if i % j == 0:

break

else:

prime_list.append(i)

return prime_list

starting_range = 2

ending_range = 7

lst = prime(starting_range, ending_range)

if len(lst) == 0:

print("There are no prime numbers in this range")

else:

print("The prime numbers in this range are: ", lst)


Program for compound interest

def compound_interest(principle, rate, time):

Amount = principle * (pow((1 + rate / 100), time))

CI = Amount - principle

print("Compound interest is", CI)

compound_interest(10000, 10.25, 5)


Pattern Printing

def Pattern(line):

pat=""

for i in range(0,line):

for j in range(0,line):

if ((j == 1 and i != 0 and i != line-1) or ((i == 0 or

i == line-1) and j > 1 and j < line-2) or (i == ((line-1)/2)

and j > line-5 and j < line-1) or (j == line-2 and

i != 0 and i != line-1 and i >=((line-1)/2))):

pat=pat+"#"

else:

pat=pat+" "

pat=pat+"\n"

return pat

line = 7

print(Pattern(line))


Program for Number of stopping station problem

def stopping_station( p, n):

num = 1

dem = 1

s = p

while p != 1:

dem *= p

p-=1

t = n - s + 1

while t != (n-2 * s + 1):

num *= t

t-=1

if (n - s + 1) >= s:

return int(num/dem)

else:

return -1

num = stopping_station(4, 12)

if num != -1:

print(num)

else:

print("Not Possible")


Check if Binary representation is Palindrome

def binaryPallindrome(num):

binary = bin(num)

binary = binary[2:]

return binary == binary[-1::-1]

if __name__ == "__main__":

num = 9

print (binaryPallindrome(num))


Check whether a number has consecutive 0’s in the given base or not

def hasConsecutiveZeroes(N, K):

z = toK(N, K)

if (check(z)):

print("Yes")

else:

print("No")

def toK(N, K):

w = 1

s = 0

while (N != 0):

r = N % K

N = N//K

s = r * w + s

w = 10

return s

def check(N):

fl = False

while (N != 0):

r = N % 10

N = N//10

if (fl == True and r == 0):

return False

if (r > 0):

fl = False

continue

fl = True

return True

N, K = 15, 8

hasConsecutiveZeroes(N, K)


Program for Number of solutions to Modular Equations

import math

def calculateDivisors (A, B):

N = A - B

noOfDivisors = 0

a = math.sqrt(N)

for i in range(1, int(a + 1)):

if ((N % i == 0)):

if (i > B):

noOfDivisors +=1

if ((N / i) != i and (N / i) > B):

noOfDivisors += 1;

return noOfDivisors

def numberOfPossibleWaysUtil (A, B):

if (A == B):

return -1

if (A < B):

return 0

noOfDivisors = 0

noOfDivisors = calculateDivisors;

return noOfDivisors

def numberOfPossibleWays(A, B):

noOfSolutions = numberOfPossibleWaysUtil(A, B)

if (noOfSolutions == -1):

print ("For A = " , A , " and B = " , B

, ", X can take Infinitely many values"

, " greater than " , A)

else:

print ("For A = " , A , " and B = " , B

, ", X can take " , noOfSolutions

, " values")

A = 26

B = 2

numberOfPossibleWays(A, B)

A = 21

B = 5

numberOfPossibleWays(A, B)


Program for Print Number series without using loop

def PrintNumber(N, Original, K, flag):

print(N, end = " ")

if (N <= 0):

if(flag==0):

flag = 1

else:

flag = 0

if (N == Original and (not(flag))):

return


if (flag == True):

PrintNumber(N - K, Original, K, flag)

return

if (not(flag)):

PrintNumber(N + K, Original, K, flag);

return

N = 20

K = 6

PrintNumber(N, N, K, True)


Program for Maximum height when coins are arranged in a triangle

def squareRoot(n):

x = n

y = 1

e = 0.000001 

while (x - y > e):

x = (x + y) / 2

y = n/x

return x

def findMaximumHeight(N):

n = 1 + 8*N

maxh = (-1 + squareRoot(n)) / 2

return int(maxh)

N = 12

print(findMaximumHeight(N))


Program to print double sided stair-case pattern

def pattern(n):

for i in range(1,n+1):

k =i + 1 if(i % 2 != 0) else i

for g in range(k,n):

if g>=k:

print(end=" ")

for j in range(0,k):

if j == k - 1:

print(" * ")

else:

print(" * ", end = " ")

n = 10

pattern(n)


Program to display Zodiac sign for given date of birth

def zodiac_sign(day, month):

if month == 'december':

astro_sign = 'Sagittarius' if (day < 22) else 'capricorn'

elif month == 'january':

astro_sign = 'Capricorn' if (day < 20) else 'aquarius'

elif month == 'february':

astro_sign = 'Aquarius' if (day < 19) else 'pisces'

elif month == 'march':

astro_sign = 'Pisces' if (day < 21) else 'aries'

elif month == 'april':

astro_sign = 'Aries' if (day < 20) else 'taurus'

elif month == 'may':

astro_sign = 'Taurus' if (day < 21) else 'gemini'

elif month == 'june':

astro_sign = 'Gemini' if (day < 21) else 'cancer'

elif month == 'july':

astro_sign = 'Cancer' if (day < 23) else 'leo'

elif month == 'august':

astro_sign = 'Leo' if (day < 23) else 'virgo'

elif month == 'september':

astro_sign = 'Virgo' if (day < 23) else 'libra'

elif month == 'october':

astro_sign = 'Libra' if (day < 23) else 'scorpio'

elif month == 'november':

astro_sign = 'scorpio' if (day < 22) else 'sagittarius'

print(astro_sign)

if __name__ == '__main__':

day = 19

month = "may"

zodiac_sign(day, month)


Write a python code to print this pattern.

 


def pattern(n):

num = 65

for i in range(0,n):

for j in range(0,i+1):

ch = chr(num)

print(ch,end = " ")

num = num + 1

print("\r")

n = 5

pattern(n)