Showing posts with label Array. Show all posts
Showing posts with label Array. Show all posts

Group Shifted String

ALPHA = 26

def getDiffString(str):

shift=""

for i in range(1, len(str)):

dif = (ord(str[i]) -

ord(str[i - 1]))

if(dif < 0):

dif += ALPHA

shift += chr(dif + ord('a'))

return shift

def groupShiftedString(str,n):

groupMap = {}

for i in range(n):

diffStr = getDiffString(str[i])

if diffStr not in groupMap:

groupMap[diffStr] = [i]

else:

groupMap[diffStr].append(i)

for it in groupMap:

v = groupMap[it]

for i in range(len(v)):

print(str[v[i]], end = " ")

print()

str = ["acd", "dfg", "wyz",

"yab", "mop","bdfh",

"a", "x", "moqs"]

n = len(str)

groupShiftedString(str, n)


Calculate City Block Distance

import numpy as np

def cityblock_distance(A, B):

result = np.sum([abs(a - b) for (a, b) in zip(A, B)])

return result

if __name__== "__main__":

arr1 = [5,2]

arr2 = [1,5]

result = cityblock_distance(arr1, arr2)

print(result)


Program to print Lower triangular and Upper triangular matrix of an array

def lower(matrix, row, col):

for i in range(0, row):

for j in range(0, col):

if (i < j):

print("0", end = " ");

else:

print(matrix[i][j],

end = " " );

print(" ");

def upper(matrix, row, col):

for i in range(0, row):

for j in range(0, col):

if (i > j):

print("0", end = " ");

else:

print(matrix[i][j],

end = " " );

print(" ");

matrix = [[1, 2, 3],

[4, 5, 6],

[7, 8, 9]];

row = 3;

col = 3;

print("Lower triangular matrix: ");

lower(matrix, row, col);

print("Upper triangular matrix: ");

upper(matrix, row, col);


Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed

def maxSum(arr):

arrSum = 0

currVal = 0

n = len(arr)

for i in range(0, n):

arrSum = arrSum + arr[i]

currVal = currVal + (i*arr[i])

maxVal = currVal

for j in range(1, n):

currVal = currVal + arrSum-n*arr[n-j]

if currVal > maxVal:

maxVal = currVal

return maxVal

if __name__ == '__main__':

arr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print ("Max sum is: ", maxSum(arr))


Range Queries for Frequencies of array elements

def findFrequency(arr, n, left, right, element):

count = 0

for i in range(left - 1, right):

if (arr[i] == element):

count += 1

return count

arr = [2, 8, 6, 9, 8, 6, 8, 2, 11]

n = len(arr)

print("Frequency of 2 from 1 to 6 = ",

findFrequency(arr, n, 1, 6, 2))

print("Frequency of 8 from 4 to 9 = ",

findFrequency(arr, n, 4, 9, 8))


Program for Counting Sort

def countSort(arr):

output = [0 for i in range(256)]

count = [0 for i in range(256)]

ans = ["" for _ in arr]

for i in arr:

count[ord(i)] += 1

for i in range(256):

count[i] += count[i-1]

for i in range(len(arr)):

output[count[ord(arr[i])]-1] = arr[i]

count[ord(arr[i])] -= 1

for i in range(len(arr)):

ans[i] = output[i]

return ans

arr = "Pythonforengineers"

ans = countSort(arr)

print ("Sorted character array is %s" %("".join(ans)))


Program for Radix Sort

def countingSort(arr, exp1):

n = len(arr)

output = [0] * (n)

count = [0] * (10)

for i in range(0, n):

index = (arr[i]/exp1)

count[int((index)%10)] += 1

for i in range(1,10):

count[i] += count[i-1]

i = n-1

while i>=0:

index = (arr[i]/exp1)

output[ count[ int((index)%10) ] - 1] = arr[i]

count[int((index)%10)] -= 1

i -= 1

i = 0

for i in range(0,len(arr)):

arr[i] = output[i]

def radixSort(arr):

max1 = max(arr)

exp = 1

while max1/exp > 0:

countingSort(arr,exp)

exp *= 10

arr = [ 170, 45, 75, 90, 802, 24, 2, 66]

radixSort(arr)

for i in range(len(arr)):

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


Program for Find remainder of array multiplication divided by n

from functools import reduce

def find_remainder(arr,n):

   sum_1=reduce(lambda x,y: x*y,arr)

   remainder=sum_1%n

   print(remainder)

arr=[100,10,5,25,35,14]

n=11

find_remainder(arr,n)

Reconstruct the array by replacing arr[i] with (arr[i-1]+1) % M

def construct(n, m, a):

ind = 0

for i in range(n):

if (a[i]!=-1):

ind = i

break

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

if (a[i]==-1):

a[i]=(a[i + 1]-1 + m)% m

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

if(a[i]==-1):

a[i]=(a[i-1]+1)% m

print(*a)

n, m = 6, 7

a =[5, -1, -1, 1, 2, 3]

construct(n, m, a)

Program for Reversal algorithm for array rotation

def rverseArray(arr, start, end):

while (start < end):

temp = arr[start]

arr[start] = arr[end]

arr[end] = temp

start += 1

end = end-1

def leftRotate(arr, d):

n = len(arr)

rverseArray(arr, 0, d-1)

rverseArray(arr, d, n-1)

rverseArray(arr, 0, n-1)

def printArray(arr):

for i in range(0, len(arr)):

print (arr[i])

arr = [1, 2, 3, 4, 5, 6, 7]

leftRotate(arr, 2)

printArray(arr)


Program to Split the array and add the first part to the end

def splitArr(arr, n, k):

for i in range(0, k):

x = arr[0]

for j in range(0, n-1):

arr[j] = arr[j + 1]

arr[n-1] = x

arr = [12, 8, 10, 11, 52, 36]

n = len(arr)

position = 2

splitArr(arr, n, position)

for i in range(0, n):

print(arr[i], end = ' ')