HackerEarth The largest subnumber problem solution

In this HackerEarth The largest sub number problem solution you are given a string S of length N which consists of digits from 0 to 9. You need to find an index i such that the sub number formed by S[i..N] is divisible by K and the xor of all the digits in the sub number formed by S[1..(i - 1)] is the maximum. If there are multiple i's such that S[i..N] is divisible by K and for all such values of S[1..(i - 1) is maximum, then print the largest sub number.


The sub number S[i..N] should not contain any leading zeros and the value of S[i..N] should not be 0. Both the sub numbers S[1..(i - 1)] and S[i..N] should contain at least one digit. If no answer exists, print -1.


HackerEarth The largest subnumber problem solution


HackerEarth The largest subnumber problem solution.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll pw[100005];
void pre(int k){
pw[0]=1;
for(int i=1;i<=100000;i++){
pw[i]=(pw[i-1]*10)%k;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
pre(k);
string s;
cin>>s;
ll prefix[n];
prefix[0]=s[0]-'0';
for(int i=1;i<n;i++) prefix[i]=(prefix[i-1]^(s[i]-'0'));
int idx=-1;
ll rem=0;
ll maxm=0;
for(int i=n-1;i>0;i--){
rem=((s[i]-'0')*pw[n-i-1]+rem)%k;
if(rem==0 && s[i]!='0'){
if(prefix[i-1]>=maxm){ idx=i; maxm=prefix[i-1]; }
}
}
if(idx==-1) cout<<"-1";
else for(int i=idx;i<n;i++) cout<<s[i];
cout<<"\n";
}
return 0;
}


second solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class LargestSubNumber {

static class FastReader {
BufferedReader br;
StringTokenizer st;

public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}

public static void main(String[] args) {

FastReader fr = new FastReader();

int t = fr.nextInt();
assert t>=1 && t<=10;
for (int i = 0; i < t; i++) {
long n,k;
n = fr.nextInt();
k = fr.nextInt();
assert n>=1 && n<=1e5;
assert k>=1 && k<=1e9;
List<Long> po = new ArrayList<>();
po.add( 1L);
for (int j = 1; j < 1e5+1; j++) {
po.add((po.get(j - 1) * (10 % k)) % k);
}
String str = fr.nextLine();
assert n == str.length();
for (int j = 0; j < str.length(); j++) {
assert str.charAt(j) >= '0' && str.charAt(j) <= '9';
}
List<Long> list = new ArrayList<>();
long xor = 0;
for (int j = 0; j < str.length(); j++) {
xor = xor^(str.charAt(j)-'0');
list.add(xor);
}

long mXor = -1;
long remain = 0;
int c = 0;
int index = -1;
int sum = 0;
for (int j = str.length() - 1; j >= 1; j--) {
remain = ((((str.charAt(j) - '0') % k) * po.get(c)) % k + remain) % k;
sum += (str.charAt(j) - '0');
if ( remain == 0) {
if (list.get(j - 1) >= mXor && sum > 0) {
mXor = list.get(j - 1);
index = j;
}
}
c++;
}
if(index == -1)
System.out.println(-1);
else {
while (index < str.length() && str.charAt(index) == '0')
index++;
if(index == str.length())
System.out.println(-1);
else {
System.out.println(str.substring(index));
}
}

}
}

}


Post a Comment

1 Comments