You are given an array A containing N integers, and a positive integer M. Find the maximum value of
A_i + A_j + ((A_i - A_j) \bmod M)
across all pairs 1 \leq i, j \leq N.
EXPLANATION:
Note that the quantity A_j + ((A_i - A_j) \bmod M) has a specific meaning: it is the smallest value larger or equal to A_j that is congruent to A_i modulo M. From this meaning, we see that regardless of our choice of A_i, our best choice of A_j is going to be the largest value in A. Therefore, the solution is just to loop over A_i, while having \max_A as A_j.
TIME COMPLEXITY:
Time complexity is O(N) per test case.
SOLUTION:
Preparer's Solution
for _ in range(int(input())):
N, M = map(int, input().split())
a = list(map(int, input().split()))
mx = max(a)
print(max([x + mx + (x - mx)%M for x in a]))
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n;
ll m;
ll a[500001];
void solve(){
cin >> n >> m;
for(int i=1; i<=n ;i++) cin >> a[i];
sort(a+1,a+n+1);
ll ans=-1e18;
for(int i=1; i<=n ;i++){
ll res=(a[i]+m-a[n]%m)%m;
ans=max(ans,a[i]+a[n]+res);
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, a[i] + a[n - 1] + ((a[i] - a[n - 1]) % m + m) % m);
}
cout << ans << '\n';
}
}
If you look at the code, you can see that the list is sorted prior to all the calculations. So the biggest value is at the end of the list, at index n-1.
I think the confusion comes from not distinguishing between the mathematical formula and the actual code. It’s not that some random A[j] = Amax, but we want A_j in the mathematical formula to be the max value. We choose A_j to be the max value. And the max value is at the end of the list, because it gets sorted.
If you have fixed A_i, then you know what mod A_j + (A_i - A_j) \bmod M should have. Suppose you take A_j that is smaller than A_{max}, then there is no way the next value of A_j should be larger than the next value of A_{max}, since you have fixed which modulo this next value should land in.
Let’s take a concrete example. Say A_i = 3, A_j = 9 and M = 5. Then A_j + (A_i - A_j) \bmod M is the smallest value larger or equal to 9 that has modulo 3 when divided by 5 (the answer is 13).
int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n;
int m;
cin>>n>>m;
int a[n];
int mx=INT_MIN;
sort(a,a+n);
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
{
int mod=abs((a[i]-a[j])%m);
int restcalculation=a[i]+a[j]+mod;
mx=max(mx,restcalculation);
}
}
cout<<mx<<endl;
}
return 0;
}
i got some test cases wrong can you help me with my approach
can you please tell me why only some of the mod variables(mod1,mod2,mod3,mod4) getting calculated? when i tried debugging , i noticed that only 1 or 2 of those lines are getting calculated in my code.
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner (System.in);
int t = sc.nextInt();
while(t!=0){
int n = sc.nextInt();
int m = sc.nextInt();
int [] a = new int [n];
for(int i=0;i<n;i++){
a[i] = sc.nextInt();
}
int def=0,sum=0, max=0;
for(int i=0;i< n -1;i++){
def =a[i] - a[n-1];
if( def < 0) def = m - ((a[n-1] - a[i]) % m );
else def = (a[i] - a[n-1]) % m;
sum =a[i] + a[n-1] + def;
if(sum>max) max = sum;
}
System.out.println(max);
t--;
}
}
}
This gave me the output but the test cases failed …
