A. In Search of an Easy Problem
As the name suggest it is an easy problem all what is needed is to take a string s as input and print "Mohamed Salah"
Time Complexity : $$$O(1)$$$
#include<iostream>
using namespace std;
int main()
{
string str;cin>>str;
cout<<"Mohamed Salah";
}
B. A Nice Array
We want to make sure that each element only occurs one time. So, We’ll make a frequency array to count how many times each element occurred. Then, we’ll loop the frequency array to make sure that each element occurred 1 time. If there’s an element that occurs more than 1 time, we break from the loop and print "NO". If the loop is finished
Time Complexity : $$$O(N)$$$
Where $$$N$$$ is the size of the frequency array
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int main(){
int t;
cin >> t;
while(t--){
int freq[N] = {0};
int n; cin >> n;
for(int i = 0; i < n; i ++){
int x; cin >> x;
freq[x]++;
}
bool flag = false;
for(int i = 0; i < N; i++){
if(freq[i] > 1){
flag = true;
break;
}
}
if(flag)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
C. P vs. NP
If $$$a$$$%$$$b=0$$$ ($$$a$$$ is divisible by $$$b$$$), just print $$$0$$$. Otherwise, we need exactly $$$b − a$$$%$$$b$$$ moves to make zero remainder of $$$a$$$ modulo $$$b$$$. % is the modulo operation.
Time Complexity : $$$O(1)$$$
#include<iostream>
using namespace std;
int main(){
int t = 1; cin >> t;
while(t--){
int a,b;
cin >> a >> b;
if(!(a%b)) cout<<"0\n";
else cout<<b-(a%b)<<"\n";
}
return 0;
}
D. Odds Vs Evens
We caculate the sum of elements at even indices and the sum of elements at odd indices. Then we compare these two numbers.
Time Complexity : $$$O(n)$$$
Where $$$n$$$ is the size of the array
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll i, n, odd = 0, even = 0;
cin >> n;
for(i = 1; i <= n; i++){
ll x; cin >> x;
if(( i%2 ))
odd += x;
else
even += x;
}
if(odd > even)
cout << "Odd" << endl;
else if(even > odd)
cout << "Even" << endl;
else
cout << "Equal" << endl;
return 0;
}
E. Pepsi can
In order to minimize the difference between the number of coins of 1 dollar $$$c1$$$ and 2 dollars $$$c2$$$, all we need to do is to divide the total number of burles $$$n$$$ by 3. Then, if the remainder from the division equals 1, increase the coins of $$$c1$$$ by one. And in case the remainder from the division is 2, then we will increase the coins of $$$c2$$$ by 1.
Time Complexity : $$$O(1)$$$ per test case.
#include<iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int c1,c2;
c1=n/3;c2=n/3;
c1+=(n%3==1);
c2+=(n%3==2);
cout<<c1<<" "<<c2<<endl;
}
return 0;
}
F. N and T
In this problem we want to find a number that is divisible by t and has n digits. But we found a series of problems:
n can be 100 -> there is no data type that handles such a big number (long long take up to pow(2,64))
How can I easily get a number divisible by t
The answer is t itself and
what about multiplying the number by 10 until I get the desired length? why 10: multiplying by 10 will keep the divisibility state (2x10 is divisible by 2 and 2x10x10 is still divisible by 2....)
so the answer will be the t multiplied by 10 until I reach the desired length. -> problem 2 solved
multiplying by 10 means adding 0 to the end of the number (2x10 = 20, 330x10 = 3300)
so we can print the t followed by zeros -> problem 1 solved
but when I will print -1? the answer is if the number of digits in t is less than n as the smallest number is divisble by t is t itself
Time Complexity : $$$O(N)$$$
#include <iostream>
#include <vector>
using namespace std ;
int32_t main() {
int n,t;cin>>n>>t;
if(t == 10 && n== 1){
cout<<"-1";
}else{
cout<<t;
n--;
if(t == 10)n--;
for (int i = 0; i < n; ++i) {
cout<<"0";
}
}
}
H. Strange Sort
The key for solving this problem is the observation that the frequency of any element will not exceed 1000 (The maximum number of elements) The solution steps will be as follows
- Sort the elements in reversed order.
- Iterate from 1 to n (number of elements) for all numbers if the frequency of number equal to i print the number i times
- This grantees that the elements is printed in the increasing order in frequency and if there is two elements with the same frequency they will be printed in decreasing order
- Here we still have one problem we can't calculate frequency for negative values in array so we will use two arrays one for positive as usual and another one for negative if the number less than zero we will store its frequency in neg_freq array in its as follows if i = -5 neg_freq[5]++;
Time Complexity : $$$O(N^2)$$$ as we iterate over all elements n times
#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main()
{
fast();
int neg_freq[1001]={0}, pos_freq[1001] = {0}; // array for positive and array for negative
int n;
cin >>n;
int a[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
if(a[i] > 0)
pos_freq[a[i]]++;
else
neg_freq[-a[i]]++;
}
sort(a, a+n);
reverse(a, a+n);
for (int i = 1; i <= n; ++i) {
for(int j = 0; j < n; j++){
if(a[j] > 0){
if(pos_freq[a[j]] == i){
for(int k = 0; k < i; k++){
cout<<a[j]<<' ';
}
pos_freq[a[j]] = 0;
}
}else{
if(neg_freq[-a[j]] == i){
for(int k = 0; k < i; k++){
cout<<a[j]<<' ';
}
neg_freq[-a[j]] = 0;
}
}
}
}
return 0;
}
I. Save Khaled's life !!!
The Solution is to check the sum for each cell. For each cell (i , j) we can iterate over all elements in its diagonals calculate the sum and save the maximum. We have four different directions to go to
- top right each cell in this direction (i, j) the next one is (i-1, j+1)
- bottom left each cell in this direction (i, j) the next one is (i+1, j-1)
- top left each cell in this direction (i, j) the next one is (i-1, j-1)
- bottom right each cell in this direction (i, j) the next one is (i+1, j+1)
here at each cell the maximum number of elements to loop over is mx(m, n) so Time Complexity : $$$O(n*m*max(n, m))$$$
#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main()
{
fast();
int t;
cin >>t;
while(t--){ // our test cases
int n, m;
cin >> n >> m;
int a[n][m];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> a[i][j];
}
}
int mx = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
int now = 0;
int ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci--;
cj--; // top left direction
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci++;
cj--; // bottom left direction
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci--;
cj++; // top right direction
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci++;
cj++; // bottom right direction
}
now-=a[i][j]*3; // we have added a[i][j] to sum 4 times. we need to add it only one time, so we subtract 3*a[i][j]
mx = max(mx, now); // save maximum sum in mx
}
}
cout << mx << endl;
}
return 0;
}
J. Salma Has Cakes and You Don't!
The problem in brief is about giving you an array of integers and some queries. Each query represents an index for an integer in the array and you need to output the number of distinct integers starting from this index till the end of the array. So, we need to count.
But, we need to count the number of distinct values, so we are just interested in the first occurrence of each value and we can neglect the other copies. However, where to start counting? Is the first occurrence of a value that we are concerned with will be the one from the left or from the right?
Well, In each query, we count till the end of the array, Which tells that the answer starting from index $$$i$$$ will be greater than or equal to the answer starting from index $$$i+1$$$ ,because if the number of distinct integers starting from index $$$i+1$$$ $$$=$$$ $$$x$$$, where x is a positive integer, then the number of distinct values starting from $$$i$$$ will be either $$$x+1$$$ (if it is the first occurrence for the value at index $$$i$$$) or $$$x$$$ (if the value at index $$$i$$$ is a copy),
So, we count starting from the right(the end of the array).
Since the answer of each index depends on the answer of the index that follows(as we stated before) we can use a prefix array (although in this case it’s better to call it a suffix array)
So, what we are going to do is starting from the end of the array and check for each value whether it’s its first occurrence or not(we can use a frequency array for this). If it is, we increment the answer for this index and if it’s not, the answer will be the same as the previous answer(which was for the index that follows)
Surely, We start counting with value $$$0$$$.
Time Complexity : $$$O(N)$$$
#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main()
{
fast();
int n, m;
cin >> n >> m;
int arr[n];
for(int i = 0; i<n; i++){
cin >> arr[i];
}
int freq[100005]={0},pref[n+1];
pref[n] = 0;
for(int i = n-1; i>=0; i--){
if(freq[arr[i]] == 0)
pref[i] = pref[i+1] + 1;
else
pref[i] = pref[i+1];
freq[arr[i]]++;
}
int q;
while(m--){
cin >> q;
cout<<pref[q-1]<<"\n";
}
return 0;
}