Zeroes at the End
Author: Mudit Mahajan
DIFFICULTY:
Easy
EXPLANATION:
A simple method is to first calculate the factorial of n, then count trailing 0s in the result (We can count trailing 0s by repeatedly dividing the factorial by 10 till the remainder is 0).
The above method can cause overflow for slightly bigger numbers, as the factorial of a number is a big number.
Observation 1: A trailing zero is always produced by prime factors 2 and 5.
Observation 2: The number of 2s in prime factors is always more than or equal to the number of 5s.
Solution: To count the total number of 5s in prime factors of n!.
SOLUTION:
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;
while(n)
{
ans += n / 5;
n /= 5;
}
cout << ans << "\n";
}
return 0;
}
Substring Reverse
Author: Mudit Mahajan
DIFFICULTY:
Easy
EXPLANATION:
The task is to reverse the substring from the index x to y. Run a while loop from for the specific index and keep swapping the characters at the starting index and the ending index of the string.
We can also use built-in reverse functions available in C++, Python etc.
SOLUTION:
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);
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
int x, y;
cin >> x >> y;
int i = x - 1;
y -= 1;
while(i <= y)
{
swap(s[i++], s[y--])
}
cout << s << " \n";
}
}
return 0;
}
Friends of Joey
Author: Anshu Sharma
DIFFICULTY:
Medium
EXPLANATION:
The GCD is the product of the common factors of the two numbers.
It is also mentioned in the constraints that the minimum of the two numbers will be at most 12.
So the solution is simply the factorial of the smaller number, as that would be all the common factors that the two numbers will have.
SOLUTION:
Setter's Solution 1(Python)
import math
a, b = map(int, input().split())
print(math.factorial(min(a, b)))
Count of Indices
Author: Mudit Mahajan
DIFFICULTY:
Easy
EXPLANATION:
The solution to check the number of indices where the elements of both the arrays are equal, as that is the only way that the both will remain a permutation.
SOLUTION:
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;
ll a[n], b[n];
for(i = 0; i < n; i++) cin >> a[i];
for(i = 0; i < n; i++) cin >> b[i];
for(i = 0; i < n; i++) if(a[i] == b[i]) ans++;
cout << ans << "\n";
}
return 0;
}
Special Index
Author: Mudit Mahajan
DIFFICULTY:
Medium
EXPLANATION:
The solution is two to create a prefix array and a suffix array which will contain the summations of elements up to that index.
Then check at each position if the value of prefix sum array is equal to suffix sum array.
SOLUTION:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
using namespace std;
ll solve(vector<ll>& nums) {
ll i, n = nums.size();
vector<ll> prefix(n), suffix(n);
for(i = 0; i < n; i++) {
if(i == 0) prefix[i] = nums[i];
else prefix[i] = prefix[i - 1] + nums[i];
}
for(i = n - 1; i >= 0; i--) {
if(i == n - 1) suffix[i] = nums[i];
else suffix[i] = suffix[i + 1] + nums[i];
}
for(i = 0; i < n; i++) {
if(prefix[i] == suffix[i]) return true;
}
return false;
}
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;
vector<ll> arr(n);
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
if(solve(arr)) cout << "YES";
else cout << "NO";
cout << endl;
}
return 0;
}
Chef and String
Author: Utkarsh Bhatnagar
DIFFICULTY:
Medium
EXPLANATION:
We have to find the maximum length string with all letter having even frequency
Let S=“abeeeeeab”
Frequency of
‘a’=2 , ‘b’=2 , ‘e’=5
So we can remove either 3 ‘e’ or 1 ‘e’ from the string to make all the letter frequency even.
Since we have to find the longest string, we remove 1 ‘e’ from the string.
Resultant string is :”abeeeeab”
SOLUTION:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
int arr[27] = {0};
for (int i = 0; i < n; i++) {
int letter = s[i] - 'a';
arr[letter]++;
}
int ans = 0;
for (int i = 0; i <= 26; i++) {
if (arr[i] % 2 != 0) ans += max(arr[i] - 1, 0);
else ans += arr[i];
}
cout << ans << endl;
}
return 0;
}
Minimum Energy
Author: Mudit Mahajan
DIFFICULTY:
Hard
EXPLANATION:
The solution requires knowledge of Prefix Sums and Sliding window technique.
The approach is to:
- Sort the array.
- Form the prefix sum array.
- For every k-sized subarray or window of the array, find the cost.
- Compare each cost and find the minimum cost among them.
SOLUTION:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
using namespace std;
int solve(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<int> prefix(n + 5);
for(int i = 0; i < n; i++) {
if(i == 0) prefix[i + 1] = nums[i];
else prefix[i + 1] = prefix[i] + nums[i];
}
int ans = INT_MAX;
for(int i = k - 1; i < n; i++) {
int temp = prefix[i + 1] - prefix[i + 1 - k];
ans = min(ans, nums[i] * k - temp);
}
return ans;
}
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;
vector<int> arr(n);
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << solve(arr, k);
cout << endl;
}
return 0;
}
Chef and Powers
Author: Utkarsh Bhatnagar
DIFFICULTY:
Hard
EXPLANATION:
Solution:
-
Generate all possible pair combinations for A,B and C,D.
-
Assume each array has length n, we will have two arrays, each with length n^2. We call it Merge1 and Merge2.
-
Sort one of our Merge array, let’s say Merge2.
-
Iterate the non-sort Merge1 array, for each its element, we want to find how many element from Merge2 can pair it up with sum less than or equal to target. We can do a binary search on it.
Time Complexity:
O(n^2) as we have a 2 Merge array. Each one will have at most O(n^2) elements.
SOLUTION:
Setter's Solution 1(C++)
#include <bits/stdc++.h>
using namespace std;
int BinarySearch(vector<int> &v, int target) {
int ans = -1, l = 0, r = v.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (v[mid] <= target) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
return ans + 1;
}
int solve(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D, int target) {
//merging A and B(making all possible combination of a[i]+b[j]) similarly with C and D
vector<int> merge1, merge2;
for (auto i : A) {
for (auto j : B)
merge1.push_back(i + j);
}
for (auto i : C) {
for (auto j : D)
merge2.push_back(i + j);
}
sort(merge2.begin(), merge2.end());
int count = 0;
for (auto i : merge1) {
if (target >= i)
count += BinarySearch(merge2, target - i);
}
return count;
}