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.

`#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));        }      }          }  } }`

1 Comments

1. Thanks bro
It perfectly works.