PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: Aryan Agarwala
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta
DIFFICULTY:
Simple
PREREQUISITES:
GCD
PROBLEM:
You are given N positive numbers A_1, A_2, ... , A_N and a positive integer K. For some integer X, let’s define Quotient and Remainder such that:
- Quotient = K/X (/ is a integer division)
- Remainder = K\%X
Among all N numbers, you have to find a number for which Reminder is zero and Quotient is the minimum possible.
QUICK EXPLANATION:
- Sort the N numbers in ascending order.
- Consider those only which have a value less than or equal to K.
- Now, you have to find the largest possible number for which Remainder is zero.
EXPLANATION:
As numbers are greater than K, they will never produce Remainder equal to zero so we need not consider them. As we want to find the number which has minimum Quotient, this indicates that we need to find the maximum number which is also the divisor of K.
So, for that, we can sort the array and find the largest number less than or equal to K which has Remainder equal to zero.
Additional
In order to get minimum steps, we need to check among all possible steps that can capture chefs. As it is given that pawns move forward, our search space reduces to those people whose pawns are initially to the left of the pawn of the chef.
For every person, the amount of forwarding steps at a time of its pawn is equal to its initial position hence we can say that if a chef’s pawn modulus people’s pawn position is equal to zero, then only that pawn can capture the chef.
In that situation by calculating no. of times that pawn has to move forward, the minimum of all will be the required answer.
TIME COMPLEXITY:
TIME: O(N)
SPACE: O(1)
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define int long long
#define INF -1
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n, k;
cin>>n>>k;
map<int, bool> factor;
int temp = sqrt(k);
for(int i = 1;i<=temp;i++){
if(k%i != 0) continue;
factor[i] = factor[k/i] = true;
}
int ans = -1;
for(int i =0 ;i<n;i++){
cin>>temp;
if(factor[temp]){
ans = max(ans, temp);
}
}
cout<<ans<<"\n";
}
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(a) ((int)(a.size()))
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
int main()
{
int T;
cin >> T;
assert(1 <= T && T <= 1000);
while(T--)
{
int n , k;
cin >> n >> k;
assert(1 <= n && n <= 1000);
assert(1 <= k && k <= INF);
int pos = -1;
for(int i = 1; i <= n; i++)
{
int p;
cin >> p;
assert(1 <= p && p <= INF);
if(k % p == 0)
pos = max(pos , p);
}
cout << pos << endl;
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n,k;
cin >> n >> k;
int ans = -1;
while(n--)
{
int x;
cin >> x;
if(ans < x && k%x == 0)
ans = x;
}
cout << ans << endl;
}
}