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

coding problems

HackerEarth The largest subnumber problem solution.

second solution

Comment