##Given an array of integers, sort the array in ascending order without

'''arr = [64, 34, 25, 12, 22, 11, 90]

for i in range(len(arr)):
for j in range(len(arr)-1-i):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
print(arr)'''
##Print the first N Fibonacci numbers. / Find the Nth Fibonacci number
'''n=int(input('Enter a Nth fibo number:'))
first=0
second=1
for i in range(n):
print(first)
t=first+second
first=second
second=t'''

##Check whether a given number is prime. / Print all prime numbers between 1 and N.
'''n=int(input('Enter a num:'))
count=0
for i in range(1,n+1):
if n%i == 0:
count+=1
if count == 2:
print('Prime')
else:
print('Not a prime')'''

##Reverse a given string without using library functions.

'''string=input('Enter a string: ')
print(string[::-1])
(OR)
s=input('Enter a string:')
out=" "
for i in range(len(s)-1,-1,-1):
out+=s[i]
print(out)'''

##Determine whether a given string or number is a palindrome.

'''pali=input('Enter a string: ')
if pali == pali[::-1]:
print('Palindrome')
else:
print('Not Palindrome', pali[::-1])'''
##Reverse the digits of an integer and print the result.
'''n=int(input('Enter a Number:'))
rev=0
while n>0:
digit = n%10
rev = rev*10+digit
n = n//10
print(rev)'''
##Check whether a given number is an Armstrong number.
'''n=int(input('Enter a Number:'))
temp=n
sum=0
while temp>0:
digit=temp%10
sum=sum+digit**3
temp=temp//10
if n == sum:
print('it is an armstrong number')
else:
print('Not an armstrong number')'''
##Find the smallest element in an array.
'''arr = [64, 34, 25, 12, 22, 11, 90]
small = arr[0]
for i in arr:
if i<small:
 small=i
print(small)'''
##Find the largest element in an array.
'''arr = [64, 34, 25, 12, 22, 11, 90]
large = arr[0]
for i in arr:
if i>large:
large=i
print(large)'''
##Given employee IDs, arrange them in ascending order.
'''emp = [104,101,108,103,102]
[Link]()
print(emp)
(OR)
emp = [104,101,108,103,102]
for i in range(len(emp)):
for j in range(len(emp)-1-i):
if emp[j]>emp[j+1]:
emp[j],emp[j+1]=emp[j+1],emp[j]
print(emp)'''
##Store employee details in a HashMap and perform insert, update, delete, and search operations.
'''emp={}
emp['101']='Waseem'
emp['102']='sara'
print(emp)
emp['101']='Mohammed'
print(emp)
del emp['102']
print(emp)
print([Link]('101'))'''
##Print all elements in a list except the number 7.
'''arr = [1, 2, 7, 4, 7, 5]
for i in arr:
if i == 7:
continue
print(i)'''
##Convert every alternate character of a string into uppercase.
'''s=input('Enter a string:')
out=""
for i in range(len(s)):
if i%2 == 0:
out+=s[i].upper()
else:
out+=s[i]
print(out)'''
##Implement stack operations (push, pop, peek, display).
'''stack=[]
[Link](10)
[Link](100)
[Link](290)
print('push:',stack)
print('peek:',stack[-1])
remove=[Link]()
print('pop:',stack)'''
##Create a linked list and insert, delete, or traverse nodes.
'''class Node:
def __init__(self, data):
[Link] = data
[Link] = None
head = Node(10)
[Link] = Node(20)
[Link] = Node(30)
temp = head
while temp:
print([Link])
temp = [Link]'''

##Print the given star or number pattern.

'''n=5
for i in range(1,n+1):
for j in range(1,n+1):
if i>j:
print('*',end='')
else:
print(' ',end='')
print()'''
##Print a pyramid using stars or numbers for a given height.
'''n=5
for i in range(1,n+1):
for j in range(1,n+1):
if (i+j) >= n+1:
print('*',end=' ')
else:
print(' ',end=' ')
for k in range(1,n+1):
if i>k:
print('*',end=' ')
else:
print(' ',end=' ')
print()'''
##Demonstrate ArrayList, HashSet, or HashMap operations.
'''s=set()
[Link](10)
[Link](20)
[Link](30)
[Link](40)
print('Set:',s)
print(20 in s)
[Link](30)
print('removed',s)'''
##Reverse the elements of a list without using built-in reverse().
'''arr=[10,20,30,40]
for i in range(len(arr)-1,-1,-1):
print(arr[i])'''
##Handle exceptions such as division by zero or invalid input using try-except.
'''try:
a=int(input('a:'))
b=int(input('b:'))
print(a/b)
except ZeroDivisionError:
print('Cannot divide using zero')
except ValueError:
print('Invalid value')'''
##GCD
'''a=20
b=30
gcd=1
for i in range(1,min(a,b)+1):
if a%i==0 and b%i==0:
gcd=i
print(gcd)'''
##LCM
'''a=12
b=18
large=max(a,b)
while True:
if large%a==0 and large%b==0:
print(large)
break
large+=1'''
##24. Factorial
'''n=int(input('Enter the number:'))
fact=1
for i in range(1,n+1):
fact*=i
print(fact)'''
##25. Remove Duplicates
'''arr=[4,5,7,8,7,8,1,2]
out=[]
for i in arr:
if i not in out:
[Link](i)
print(out)'''
##26. Count Vowels
'''s=input('Enter a value:')
count=0
for i in s:
if i in 'AEIOUaeiou':
count+=1
print(count)'''
##27. Count sentence
'''s=input('Enter sentence:')
count=0
for i in [Link]():
count+=1
print(count)'''
##29. Second Largest
'''arr=[10,40,60,20,30]
first=second=arr[0]
for i in arr:
if i>first:
second=first
first=i
elif i>second and i!=first:
second=i
print(second)'''
##Merge array
'''a=[1,2,3]
b=[4,5,6]
c=a+b
print(c)'''
##Two Sum Question: Given an array of integers and a target K, find two numbers whose sum equals K. Print the pair; if
'''arr=[14,5,9,2,18,11,7,20,4,13]
Target=25
found=False
for i in range(len(arr)):
for j in range(i+1,len(arr)):
if arr[i]+arr[j]==Target:
print(arr[i],arr[j])
found=True
break
if found:
break
if found==False:
print('-1')'''
##2. Move All Zeros to the End Question: Move all zero elements to the end while maintaining the order of non-zero ele
'''a=[0,8,3,0,6,0,1,5,2,9]
out=[]
for i in a:
if i!=0:
[Link](i)
for i in a:
if i==0:
[Link](i)
print(out)'''
##3. Missing Number Question: Given numbers from 1 to N with one missing, find the missing number.
'''a=[10,20,30,50]
n=50
for i in range(10,n+1,10):
if i not in a:
print('missing:',i)
break'''
##4. Pair with Minimum Absolute Difference Question: Find the pair having the smallest absolute difference.
'''arr=[4,2,1,8,6]
[Link]()
small=arr[1]-arr[0]
a=arr[0]
b=arr[1]
for i in range(len(arr)-1):
diff=arr[i+1]-arr[i]
if diff<small:
small=diff
a=arr[i]
b=arr[i+1]
print(a,b)'''
##5. Majority Element
'''arr=[2,2,1,2,3,3,3,3]
for i in arr:
if [Link](i)>len(arr)//2:
print(i)
break
else:
print('No majority element')'''
##6. Single Non-Repeating Number
'''arr=[2,2,1,2,3,3,3,3,4]
for i in arr:
if [Link](i)==1:
print(i)'''
##7. Product of Array Except Self
'''arr=[4,2,1,8,6]
out=[]
for i in range(len(arr)):
pro=1
for j in range(len(arr)):
if i!=j:
pro*=arr[j]
[Link](pro)
print(out)'''
##sum of array except self
'''arr=[4,2,1,8,6]
out=[]
for i in range(len(arr)):
sum=0
for j in range(len(arr)):
if i!=j:
sum+=arr[j]
[Link](sum)
print(out)'''
##8. Maximum Subarray Sum
'''arr=[2,-3,4,-1,2,1,-5,4]
max_sum=arr[0]
for i in range(len(arr)):
total=0
for j in range(i,len(arr)):
total=total+arr[j]
if total>max_sum:
max_sum=total
print(max_sum)'''
##9. Maximum Product Subarray
'''arr=[2,-3,4,-1,2,1,-5,4]
max_prd=arr[0]
for i in range(len(arr)):
pro=1
for j in range(i,len(arr)):
pro=pro*arr[j]
if pro>max_prd:
max_prd=pro
print(max_prd)'''
##10. Merge Overlapping Intervals
'''arr = [[1,3],[2,6],[8,10],[15,18]]
[Link]()
out=[]
for i in arr:
if out==[]:
[Link](i)
else:
 last=out[-1]
if i[0]<=last[1]:
if i[1]>last[1]:
last[1]=i[1]
else:
[Link](i)
print(out)'''
##1. Reverse Every Word
'''s = input('Enter a word:')
word=''
out=''
for ch in s:
if ch!='':
word=word+ch
else:
rev=''
for i in range(len(word)-1,-1,-1):
rev=rev+word[i]
out=out+rev+''
word=''
rev=''
for i in range(len(word)-1,-1,-1):
rev=rev+word[i]
out=out+rev+''
print(out)
(or)
s = input('Enter a word:')
words=[Link]()
out=[]
for i in words:
[Link](i[::-1])
print(''.join(out))'''
##2. Check Substring
'''s1='Python Programming'
s2='gram'
if s2 in s1:
print('s2 is a substring of s1')
else:
print('Not a substring')'''
##3. Check Anagram
'''s1='silent'
s2='listen'
s1=[Link]()
s2=[Link]()
if s1==s2:
print('Anagram')
else:
print('Not an anagram')'''
##4. First Non-Repeating Character
'''s = "aabbcdde"
for i in s:
count=0
for j in s:
if i==j:
count+=1
if count==1:
print(i)
break
(OR)
s = "aabbcdde"
for i in s:
if [Link](i)==1:
print(i)
break'''
##5. Count Word Frequencies
'''s = "hi hello hi python hello hi"
word=[Link]()
out={}
for i in word:
 if i not in out:
out[i]=1
else:
out[i]+=1
print(out)'''
##6. Longest Substring Without Repeating Characters
'''s = 'abcabcbb'
long=0
for i in range(len(s)):
temp=''
for j in range(i,len(s)):
if s[j] not in temp:
temp=temp+s[j]
if len(temp)>long:
long=len(temp)
else:
break
print(long)'''
##1. Valid Parentheses
'''s = '{[()]}'
stack = []
flag = True
for ch in s:
if ch == '(' or ch == '[' or ch == '{':
[Link](ch)
else:
if stack==[]:
flag=False
break
top=[Link]()
if ch==')' and top !='(':
flag = False
break
elif ch=='}' and top !='{':
flag=False
break
elif ch==']' and top !='[':
flag = False
break
if flag and stack==[]:
print("Valid")
else:
print("Invalid")'''
##2. Next Greater Element
'''arr = [8, 3, 10, 2, 5, 7, 9, 1, 6, 4]
for i in range(len(arr)):
found=False
for j in range(i+1,len(arr)):
if arr[j]>arr[i]:
print(arr[i],'->',arr[j])
found=True
break
if found==False:
print(arr[i],'->',-1)'''
##3. Kth Largest Element
'''arr = [8, 3, 10, 2, 5, 7, 9, 1, 6, 4, 20, 18]
k=int(input("Enter which kth largest number you want:"))
[Link]()
count=1
for i in range(len(arr)-1,-1,-1):
if count==k:
print(arr[i])
break
count+=1'''
##Linear Search in Rotated Array
'''arr = [4,5,6,7,0,1,2]
target=2
found=False
for i in range(len(arr)):
 if arr[i]==target:
print('found in index',i)
found=True
break
if found==False:
print('-1')'''
##Postfix exxpression
'''exp = '23+5*'
stack=[]
for ch in exp:
if [Link]():
[Link](int(ch))
else:
b=[Link]()
a=[Link]()
if ch == '+':
[Link](a+b)
elif ch == '-':
[Link](a-b)
elif ch== '*':
[Link](a*b)
elif ch=='/':
[Link](a/b)
print(stack)'''
##1. Rotate Array by K
'''arr = [1,2,3,4,5]
k=int(input('Enter the k value to rotate:'))
n=len(arr)
k=k%n
out=[]
for i in range(n-k,n):
[Link](arr[i])
for i in range(0,n-k):
[Link](arr[i])
print(out)'''
##2. Longest Consecutive Sequence
'''arr = [100,4,200,1,3,2]
[Link]()
count=1
maxi=1
for i in range(len(arr)-1):
if arr[i]+1 == arr[i+1]:
count+=1
elif arr[i] == arr[i+1]:
continue
else:
if count>maxi:
maxi=count
count=1
if count>maxi:
maxi=count
print(maxi)'''
#Group anagrams
'''arr=['eat','tea','tan','ate','nat','bat']
out={}
for word in arr:
key=''.join(sorted(word))
if key not in out:
out[key]=[]
out[key].append(word)
for i in [Link]():
print(i)'''
##LRU cache simulation
'''cache=[]
size=3
arr=[1,2,3,1,4,5]
for i in arr:
if i in cache:
[Link](i)
 [Link](i)
else:
if len(cache)==size:
[Link](0)
[Link](i)
print(cache)'''