PROBLEM STATEMENT :

You have given 4 numbers A, B, C, D and you have to perform an algorithm:-

int sum=0;

for(int i=A;i<=B;i++) {

for(int j=C;j<=D;j++)
    sum+=i^j;

}

As the sum could be very large, compute it modulo 1000000007 (10e9+7).

Constraints : 1<=A,B,C,D<=1000000000

Time Limit — 1 sec

INPUT :- 4 integers A,B,C,D is given.

OUTPUT :- Print the sum after performing the algorithm.

EXAMPLE INPUT:- 1 2 3 4

EXAMPLE OUTPUT:- 14

EXPLANATION :- 1^3+1^4+2^3+2^4

2 + 5 + 1 + 6 = 14

This problem was asked in my recent coding round of Uber. Can anyone help me with its approach?

Defining substring For a string P with characters P1, P2 ,…, Pq, let us denote by P[i, j] the substring Pi, Pi+1 ,…, Pj.

Defining longest common prefix LCP(S1, S2 ,…, SK), is defined as largest possible integer j such that S1[1, j] = S2[1, j] = … = SK[1, j].

You are given an array of N strings, A1, A2 ,…, AN and an integer K. Count how many indices (i, j) exist such that 1 ≤ i ≤ j ≤ N and LCP(Ai, Ai+1 ,…, Aj) ≥ K. Print required answer modulo 109+7.

Note that K does not exceed the length of any of the N strings. K <= min(len(A_i)) for all i

For example,

A = ["ab", "ac", "bc"] and K=1.

LCP(A[1, 1]) = LCP(A[2, 2]) = LCP(A[3, 3]) = 2 LCP(A[1, 2]) = LCP("ab", "ac") = 1 LCP(A[1, 3]) = LCP("ab", "ac", "bc") = 0 LCP(A[2, 3]) = LCP("ac", "bc") = 0

So, answer is 4. Return your answer % MOD = 1000000007

Constraints 1 ≤ Sum of length of all strings ≤ 5*10^5 Strings consist of small alphabets only.

Can someone tell me how would I approach this problem?