In this HackerEarth Maximize the modulo function problem solution You are given an integer N that is represented in the form of string S of length M. You can remove at most 1 digit from the number after removing the rest of the digits that are arranged in the same order.
HackerEarth Maximize the modulo function problem solution.
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int power(int a, int b, int k)
{
if(b == 0) return 1;
int ans = 1;
int val = a;
while(b)
{
if(b%2)
{
ans *= val;
ans %= k;
}
val *= val;
val %= k;
b /= 2;
}
return ans;
}
void solve(){
int m, k;
cin >> m >> k;
string s;
cin >> s;
int mod_val = 0;
for(int i = 0 ; i < m ; i++)
{
int digit = s[i] - 48;
mod_val = (mod_val + (digit*power(10, m - i - 1, k)%k))%k;
}
int prev = 0;
int answer = mod_val;
for(int i = 0 ; i < m ; i++)
{
int digit = s[i] - 48;
mod_val = (mod_val - (digit*power(10, m - i - 1, k))%k + k)%k;
answer = max(answer, (prev + mod_val)%k);
prev = (prev + (digit*power(10, m - i - 2, k))%k)%k;
}
cout << answer << endl;
}
signed main(){
int t;
cin >> t;
while(t--){
solve();
}
}
Second solution
t = int(input())
while t > 0:
t -= 1
m, k = map(int, input().split())
n = input()
pre = [0]
for c in n:
pre += [(pre[-1] * 10 + int(c)) % k]
ans = pre[-1]
suf = 0
cur_pow = 1
for i in range(m - 1, -1, -1):
ans = max(ans, (pre[i] * cur_pow + suf) % k)
suf += cur_pow * int(n[i])
suf %= k
cur_pow = cur_pow * 10 % k
print(ans)
0 Comments