String Relation
Author: Devansh Goel
DIFFICULTY:
Cakewalk
PROBLEM:
There are two strings s1 and s2. There exists a relation between s1 and s2.
For ex- if s1 is AGH then s2 will be BHI.
We can clearly see that B comes after A, H comes after G and I comes after H.
Find s2 with the help of s1 following the same relation.
SOLUTION:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t=0,len=0,i=0;
string s;
cin>>t;
while(t)
{
cin>>len;
cin>>s;
for(i=0;i<len;i++)
{
cout<<char(s[i]+1);
}
cout<<"\n";
t--;
}
return 0;
}
Setter's Solution 2(Python)
try:
t= int(input())
while t:
length= int(input())
s= input()
#going through all the characters in the string
#ord function returns the ascii value of a character
#chr function returns the character with given ascii value
for char in s:
print(chr(ord(char)+1),end='')
print()
t-=1
except:
pass
Oxymoron of a Number:
Author: Mudit Mahajan
DIFFICULTY:
Easy
PROBLEM:
Chef has a number N.
Chef likes oxymoron and he has devised a way to combine his love of oxymoron and number N.
According to him, a number is an oxymoron if:
- It is even and the sum of all digits of the number is odd, or
- It is odd and the sum of all digits of the number is even.
That is, if N = 17, the number is odd but the sum (8) is even, or if N = 36, the number is even but the sum (9) is odd.
For t numbers, find out if the number is an oxymoron.
If it is print YES else NO.
EXPLANATION:
This is a simple enough problem.
Find the sum of all the digits in the number and then check if sum is odd and the number is even or if sum is even and number is odd.
SOLUTIONS:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll test;
cin >> test;
while(test--)
{
ll i, j, k, n, temp, count = 0, ans = 0, sum = 0;
cin >> n;
k = n;
while(n > 0)
{
temp = n % 10;
sum += temp;
n /= 10;
}
if((k % 2 and sum % 2 == 0) || (k % 2 == 0 and sum % 2))
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
Setter's Solution 2(Python)
try:
#input the no. of test cases
t= int(input())
#running all the test cases
while t:
#input the number
num= int(input())
#find the sum of digits of given number
s=0
temp=num
while temp:
s=s+temp%10
#print(s)
temp=int(temp/10)
#print(temp)
#check if sum is odd and number is even
#or sum is even and number is odd
if (s%2!=0 and num%2==0) or (s%2==0 and num%2!=0):
print('YES')
else:
print('NO')
t-=1
except:
pass
Minimum Sum
Author: Devansh Goel
DIFFICULTY:
Easy
PROBLEM:
There is an array of N integers. But, Chef is interested in X integers of the array such that their sum in minimum.
Find the minimum possible sum of X integers. Array can contain negative elements.
EXPLANATION:
Sort the array in ascending order.
Choose first X elements from this sorted array.
After that, add these elements.
SOLUTION:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int test_case=0,n=0,x=0,i=0,min_sum=0;
cin>>test_case;
while(test_case)
{
cin>>n>>x;
int arr[n];
for(i=0;i<n;i++) cin>>arr[i];
//sort the array
sort(arr,arr+n);
for(i=0;i<x;i++) min_sum+=arr[i];
cout<<min_sum<<"\n";
min_sum=0;
test_case--;
}
return 0;
}
Setter's Solution 2(Python)
try:
#input the no. of test cases
t= int(input())
#running all the test cases
while t:
#input the length of array and value of x
length,x= map(int,input().split(' '))
#input the array
arr= list(map(int,input().split(' ')))
#sort the array in ascending order
arr.sort()
ans=sum(arr[:x])
#print final answer
print(ans)
t-=1
except:
pass
Non Prime
Author: Devansh Goel
DIFFICULTY:
Easy
PROBLEM:
Chef has a list which consists of time required to cook n dishes.
Chef hates prime no. and therefore not cooks the dish which requires time which is prime. But, Chef is weak in mathematics.
You are Chef’s friend. Help him to solve this problem.
Find the no. of dishes Chef would like to cook.
EXPLANATION:
Find the no. of prime numbers in array.
Then, subtract no. of prime numbers from the length of total array.
SOLUTION:
Setter's Solution 1(C++)
#include <iostream>
using namespace std;
int main() {
//input the no. of test cases
int t=0,n=0,i=0,j=0,prime=0;
scanf("%d",&t);
//running all the test cases
while(t)
{
//input the size of array
scanf("%d",&n);
//input the array
int arr[n];
for(i=0;i<n;i++) scanf("%d",&arr[i]);
//get the count of prime numbers
prime=0;
for(i=0;i<n;i++)
{
//check for prime no.
j=2;
while(j<arr[i])
{
if(arr[i]%j==0)
{
break;
}
j++;
}
if(j==arr[i]) prime++;
}
printf("%d\n",n-prime);
t--;
}
return 0;
}
Setter's Solution 2(Python)
try:
t= int(input())
while t:
#input the length of array
length= int(input())
#input the array
arr= list(map(int,input().split(' ')))
prime=0
j=0
for num in arr:
for j in range(2,num):
if num%j==0:
break
if j==num-1:
prime+=1
print(length-prime)
t-=1
except:
pass
Cookies:
Author: Utkarsh Bhatnagar
DIFFICULTY:
Easy
PROBLEM:
Adam is the cook at the farewell party. He has to prepare cookies that can be distributed to the guests but he does not know the exact number of guests coming to the party. He knows that either A or B number of guests will arrive at the party.
At the party, each guest will receive one or more cookies.
As adam has a limited supply.
Find the minimum number of cookies that can be evenly distributed to the guests in both of the cases predicted.
We assume that cookies cannot be divided and distributed to multiple guests.
EXPLANATION:
Since we have to find the minimum number of cookies required and each guest will get atleast 1 cookie.
So we can find the LCM of A and B to know the minimum number of cookies that can be distributed.
SOLUTIONS:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int main()
{
FIO;
int a, b;
cin >> a >> b;
ll ans = __gcd(a, b);
ans = (a * 1ll * b) / ans;
cout << ans;
return 0;
}
Setter's Solution 2(Python)
try:
num1,num2= map(int,input().split(' '))
result=1
temp=2
while num1!=1 or num2!=1:
if num1%temp==0 or num2%temp==0:
result= result*temp
if num1%temp==0:
num1= num1/temp
if num2%temp==0:
num2= num2/temp
if num1%temp!=0 and num2%temp!=0:
temp+=1
print(result)
except:
pass
Setter's Solution 3(Python)
try:
import math
num1,num2= map(int,input().split(' '))
print(int(num1*num2/math.gcd(num1,num2)))
except:
pass
Virtual Cricket:
Author: Mudit Mahajan
DIFFICULTY:
Easy
PROBLEM:
Chef is making a cricket team for a Virtual Cricket League (VCL) tournament.
He needs to pick A batsmen and B bowlers from a pool of players which contains N batsmen as well as N bowlers.
Help him find the number of ways he can choose a team from N batsmen and N bowlers by choosing A batsmen and B bowlers.
Answer for t test cases.
EXPLANATION:
This is a simple Permutation and Combination problem.
We need to find the number of ways to choose batsmen and the number of ways to choose bowlers and the product of the two will be our answer.
Th different number of ways can be found with the combination formula : nCr = n! / ((n - r)! * r!), where ‘!’ denotes factorial.
A simple factorial function can be written for the formula.
SOLUTIONS:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
ll fact(ll n)
{
ll factorial = 1;
for(ll i = 1; i <=n; ++i)
{
factorial *= i;
}
return factorial;
}
int main()
{
ll t;
cin>>t;
ll n,x,y;
ll first,second;
while(t--)
{
cin >> n >> x >> y;
first = fact(n) / (fact(x) * fact(n - x));
second = fact(n) / (fact(y) * fact(n - y));
cout << first * second << endl;
}
return 0;
}
Setter's Solution 2(Python)
try:
#finding the no. of possible combinations
def combination(n, r):
return (fact(n) / (fact(r)* fact(n - r)))
#finding the factorial
def fact(n):
result = 1
for i in range(2, n+1):
result = result * i
return result
testcase=int(input())
for i in range(testcase):
N,A,B= list(map(int,input().split(' ')))
print(int(combination(N,A)*combination(N,B)))
except:
pass
Minimum Number:
Author: Utkarsh Bhatnagar
DIFFICULTY:
Cake Walk
PROBLEM:
Given two numbers A and B . Concatenate these two numbers to form a minimum number.
example:
A=23 B=45
after concatenation, 2345
EXPLANATION:
We have 2 number of A and B .
So their are only two possibilities A+B and B+A. And we can form both of them and check which is bigger.
To make it easier we can take input as a string and concatenate them than convert them to integer and check.
SOLUTIONS:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int main()
{
FIO;
int t;
cin >> t;
while (t--) {
string a, b;
cin >> a >> b;
string num1 = a + b, num2 = b + a;
ll al = stoll(num1), bl = stoll(num2);
if (al <= bl)
cout << al << endl;
else
cout << bl << endl;
}
return 0;
}
Setter's Solution 2(Python)
try:
#input the no. of test cases
t= int(input())
for i in range(t):
#input the numbers
num1, num2= map(int,input().split(' '))
#possible combination
a1= str(num1)+str(num2)
a2= str(num2)+str(num1)
if int(a1)<int(a2):
print(a1)
else:
print(a2)
except:
pass
Hilly Problem:
Author: Mudit Mahajan
DIFFICULTY:
Medium
PROBLEM:
Chef got bored at home so he decided to goto the top of mountain via helicopter and than start his decent from the mountain.
But he can only go to next hill if it’s height is either same as the one that Chef is currently on or if it is less than that.
If the height of the next hill is more than the current height, then he cannot go to the next hill and will be stuck there.
Chef can start from any hill.
You are given the height Hi of the mountains, you have to find the longest decent Chef can go on right side of the from any give mountain.
Chef can start from any hill and stop at any hill on the right side from where he started, i.e. , it is not necessary for him to reach the end of the mountains.
The height of the i-th hill from the left is Hi.
EXPLANATION:
The answer to this problem is very similar to prefix sum in which instead of the sum of elements we will consider the number of elements themselves which meet the given condition.
Since we can land on any hill and go from there we need to find the longest sub-array of hills which decreases or remains same as we go from left to right.
In the solution below, we take a different array and if the the hill at the i-th position satisfies the condition, we will mark it as 1, else it will remain 0. Note that for 0-th hill it will always be 0.
Then we will keep adding the consecutive 1’s that we will find with the help of prefix sum, but only if the current hill also satisfies the condition and is 1, else we will start all over again from 0.
The maximum element will be our answer.
SOLUTIONS:
Setter's Solution 1(C++)
#include "bits/stdc++.h"
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector <int> H(n), P(n);
for(int i=0; i<n; i++) cin >> H[i];
for(int i=1; i<n; i++) if(H[i-1] >= H[i]) P[i] = 1;
for(int i=1; i<n; i++) if(P[i]) P[i] += P[i-1];
cout << *max_element(P.begin(), P.end()) << "\n";
}
Setter's Solution 2(Python)
#input the no. of hills
n= int(input())
#input the height of each hill
height= list(map(int,input().split()))
p= list()
p.append(0)
for i in range(1,n):
if height[i-1]>=height[i]:
p.append(1)
else:
p.append(0)
for i in range(1,n):
if p[i]:
p[i]= p[i]+p[i-1]
print(max(p))
Bottled Water:
Author: Mudit Mahajan
DIFFICULTY:
Medium
PROBLEM:
Chef has n bottles lined up in a row. Initialized th i-th bottle contains ai millilitres of water.
Chef can pour water from one bottle to another in one operation. He will choose two bottles a and b (a shouldn’t be empty) and pour any possible amount of water (possibly, all water) from a to b.
The bottles have infinite capacity and can contain any amount of water.
He can perform the above operation at most k times.
Find the difference between the maximum and minimum amount of water in the bottles after at most k operations.
Answer for t test cases.
EXPLANATION:
In the problem we need to find the maximum difference between the maximum possible amount of water and the minimum amount of water.
In short, we need to find the maximum and minimum amount of water after k operations.
We will sort the array first as we can transfer the water from any bottle without regard to their positions.
After sorting we will take the maximum to be the sum of the k largest elements according to our operation. The water in the bottles after the operation will be zero.
Now we need to find the minimum amount of water which will be zero, in most cases, as we have transferred water but we can find the minimum amount of water in linear time by passing through the entire array as well.
The difference between them will be the answer.
SOLUTIONS:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll test;
cin >> test;
while(test--)
{
ll i, j, k, n, temp, count = 0, ans = 0, sum = 0;
cin >> n >> k;
ll arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n, greater<ll>());
for(i = 0; i <= k; i++)
{
sum += arr[i];
arr[i] = 0;
}
temp = *min_element(arr, arr + n);
ans = sum - temp;
cout << ans << endl;
}
return 0;
}
Setter's Solution 2(Python)
try:
t= int(input())
for i in range(t):
#input the no. of water bottles
#and no. of operations
n_bottle,k= map(int,input().split())
#input the amount of water in each bootle
w_amount= list(map(int,input().split()))
#sort the w_amount list in descending order
w_amount.sort(reverse=True)
#total amount of water transferred in k operations
if k<n_bottle:
total= sum(w_amount[:k+1])
else:
total= sum(w_amount[:k])
#difference between maximum and minimum will be total-0
print(total)
except:
pass
Lift Problem:
Author: Mudit Mahajan
DIFFICULTY:
Medium
PROBLEM:
There are n people in an office who want to get on lift to get to their respective floors.
There are n lifts available and all the people will get in the lift at the same time.
One lift may have two people at most and additionally, the total weight in the lift should not exceed x.
You are given the weight of each person (w1, w2, …, wn), find the minimum number of lifts that will be required.
EXPLANATION:
We need to find the minimum number of lifts required.
We will first sort the array for the weights and then we will use a basic two-pointer concept.
In two-pointer method, we will use two pointers to the array and then update their values according to the conditions specific to the problem.
In this we will use a pointer form the end (largest weights) and one from the start (smaller weights).
Since we will use two pointers, one from the beginning and one from the end, we will run a loop where the beginning pointer is always less than or equal to the end pointer.
If the sum of the two pointer weights is less than x, they will be assigned one lift else the weight that exceeds x will be assigned one lift.
SOLUTIONS:
Setter's Solution 1(C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
int main()
{
ll n, x, i;
cin >> n >> x;
ll arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n);
ll ans = 0;
ll j;
i = 0;
j = n - 1;
while(i <= j)
{
if(arr[i] + arr[j] <= x)
{
i++;
j--;
}
else
{
j--;
}
ans++;
}
cout << ans << endl;
return 0;
}
Setter's Solution 2(Python)
#input the no. of lifts and weight limit in each lift
n,x= map(int,input().split())
#input the weight of each person
weight= list(map(int,input().split()))
#to calulate minimum no. of lifts required
result=0
temp=0
i=0
j=0
while i<n:
temp=0
j=i
#j<i+2- one lift can only be used by two persons at a time
while j<i+2 and j<n and temp+weight[j]<=x:
temp= temp+weight[j]
j+=1
i=j
result+=1
print(result)