HackerEarth The largest subnumber problem solution YASH PAL, 31 July 2024 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. #include <bits/stdc++.h>#define ll long longusing 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)); } } } } } coding problems