The largest subnumber

 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[\mathrm{1..}(i-1)]$ is maximum. If there are multiple $i^{\prime }s$ such that $S[i..N]$ is divisible by $K$ and for all such values of $i$, $S[\mathrm{1..}(i-1)]$ is maximum, then print the largest sub number.

(For example: If the string is 611234, then for i = 2, two sub number will be [6], [11234] and for i = 3, two sub number will be [61], [1234], for i = 4, two sub number will be [611], [234] and so on. So you have to select $i$ such that 2nd sub number should be divisible by a given integer $K$, and bitwise xor of all the digits of the 1st sub number is maximum. If there multiple $i$ then print the largest 2nd 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[\mathrm{1..}(i-1)]$ and $S[i..N]$ should contain at least one digit. If no answer exists, print $-1$.

Example:

Input:
6 2
611234
Output:
1234

Approach

Java

public class LargestSubnumber {
    static int position[] = new int[100005];

    public static void preComputing(int k) {
        position[0] = 1;
        for (int i = 1; i < position.length; ++i) {
            position[i] = (position[i - 1] * 10) % k;
        }
    }

    public static void main(String[] args) {
        int N = 6;
        int K = 2;
        String input = "611234";
        int prefix[] = new int[N];
        prefix[0] = input.charAt(0) - '0';
        for (int index = 1; index < N; ++index) {
            prefix[index] = prefix[index - 1] ^ (input.charAt(index) - '0');
        }
        int rem = 0;
        int maximum = 0;
        int resultingIndex = N;
        preComputing(K);
        for (int i = N - 1; i > 0; i--) {
            rem = (((input.charAt(i) - '0') * position[N - i - 1]) + rem) % K;
            if (rem == 0 && prefix[i - 1] >= maximum && input.charAt(i) != '0') {
                maximum = prefix[i - 1];
                resultingIndex = i;
            }
        }
        if (resultingIndex == N) {
            System.out.println("-1");
        } else {
            String result = input.substring(resultingIndex);
            int nonZeroIndex = 0;
            for (int i = 0; i < result.length(); ++i) {
                if (result.charAt(i) != '0') {
                    nonZeroIndex = i;
                    break;
                }
            }
            System.out.println(result.substring(nonZeroIndex));
        }
    }

}