PROGRAMMING
1.
Problem statement
Given an array A[] of size N. You can replace any number in the array with the gcd of that element with
any of its adjacent elements.Print the minimum number of such operation to make the element of
whole array equal to 1. If its not possible print -1.
Input Format
First line contains n-the size of array. Next line of input contains n integers the n elements of array.
Constraints
1<=n<=10000
1<=elements of array<=10000
Output Format
Print the minimum number of such operation to make the element of whole array equal to 1. If its not
possible print -1.
PYTHON SOLUTION :
def __gcd(a,b):
if (a == 0):
return b
return __gcd(b % a, a)
def minimumMoves(A,N):
one = 0
for i in range(N):
if (A[i] == 1):
one+=1
if (one != 0):
return N - one
minimum = +2147483647
for i in range(N):
g = A[i] # to calculate GCD
for j in range(i + 1,N):
g = __gcd(A[j], g)
if (g == 1):
minimum = min(minimum, j - i)
break
if (minimum == +2147483647):
return -1
else:
return N + minimum - 1;
m=int(input())
A = list(map(int,input().split()))
N = len(A)
print(minimumMoves(A, N))
2.
Problem statement
Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents
a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of
time, the CPU could complete either one task or just be idle.
However, there is a non-negative integer n that represents the cooldown period between two same
tasks (the same letter in the array), that is that there must be at least n units of time between any two
same tasks.
Print the least number of units of times that the CPU will take to finish all the given tasks.
Input Format
First line of input contains n-the size of array. Next line of input contains n characters-the elements of
the array. Next line contains a non-negative integer n that represents the cooldown period between
two same tasks (the same letter in the array), that is that there must be at least n units of time
between any two same tasks.
Constraints
1 <= task.length <= 10^4
tasksi is upper-case English letter.
The integer n is in the range 0, 100.
Output Format
Print the least number of units of times that the CPU will take to finish all the given tasks.
PYTHON SOLUTION :
from collections import defaultdict
class Solution:
def leastInterval(self, tasks, n: int) -> int:
len_tasks = len(tasks)
if n == 0:
return len_tasks
task_counts = defaultdict(int)
for task in tasks:
task_counts[task] += 1
counts_list = [task_counts[task] for task in task_counts]
max_count = max(counts_list)
max_count_tasks = counts_list.count(max_count)
cpu_units = len_tasks
if max_count_tasks <= n:
cpu_units = (n + 1) * (max_count - 1) + max_count_tasks
return max(len_tasks, cpu_units)
a=int(input())
b=input().split()
c=int(input())
v=Solution()
print(v.leastInterval(b,c))
3.
Problem statement
Given a number N, the task is to count minimum steps to minimize it to 1 according to the following
criteria:
If N is divisible by 2 then you may reduce N to N/2. If N is divisible by 3 then you may reduce N to N/3.
Otherwise, Decrement N by 1.
Input Format
A single line of input contains integer N.
Constraints
1 ≤ N ≤ 10^5
Output Format
Print minimum steps to minimize it to 1 according to the given criteria.
PYTHON SOLUTION :
class Solution:
def minSteps(self, N):
ans = 0
dp = [-1]*100001
if(N == 1):
return 0
dp[1] = 0
for i in range(2, N+1):
op1, op2, op3 = 10000000, 10000000, 10000000
if i % 3 == 0:
op3 = dp[i//3]
if i % 2 == 0:
op2 = dp[i//2]
op1 = dp[i-1]
dp[i] = min(op1, op2, op3) + 1
ans = dp[N]
return ans
N = int(input())
ob = Solution()
ans = ob.minSteps(N)
print(ans)
Post a Comment