# Codechef: The Chefora Spell

This is the question currently I am trying to solve of codechef and I am able to get the given test cases result but I am getting Time Limit Exceeded when I am trying to submit. Please let me know what can i do in my code given below to make it more optimized.

Chef and his friend Bharat have decided to play the game "The Chefora Spell".

In the game, a positive integer $$\N\$$ (in decimal system) is considered a "Chefora" if the number of digits $$\d\$$ is odd and it satisfies the equation

$$\N=\displaystyle\sum_{i=0}^{d−1} N_{i} ⋅10^i\$$,

where $$\N_i+\$$ is the $$\i\$$-th digit of $$\N\$$ from the left in 0-based indexing.

Let $$\A_i\$$ denote the i-th smallest Chefora number.

They'll ask each other $$\Q\$$ questions, where each question contains two integers $$\L\$$ and $$\R\$$. The opponent then has to answer with

$$\(\displaystyle \prod _{i=L+1}^{R} (A_{L})^{ A_{i}})mod 10^{9}+7.\$$

Bharat has answered all the questions right, and now it is Chef's turn. But since Chef fears that he could get some questions wrong, you have come to his rescue!

## Input

The first line contains an integer $$\Q\$$ - the number of questions Bharat asks. Each of the next $$\Q\$$ lines contains two integers $$\L\$$ and $$\R\$$.

## Output

Print $$\Q\$$ integers - the answers to the questions on separate lines.

## Constraints

$$\1≤Q≤10^5\$$

$$\1≤L

$$\1≤Q≤5⋅10^3\$$

$$\1≤L

Original constraints

## Sample Input

2
1 2
9 11


## Sample Output

1
541416750


## Code



import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
StringTokenizer st;
}
String next(){
while(st == null || !st.hasMoreElements()){
try{
}catch(Exception e){
System.out.println(e);
}
}
return st.nextToken();
}
public long nextLong(){
return Long.parseLong(next());
}
}
public static void main (String[] args) throws java.lang.Exception
{

long Q = fr.nextLong();
while(Q-->0){
long num = 0;long sol = 0;
long L = fr.nextLong();
long R = fr.nextLong();
long temp = 0;
int numDigits = countDigit(L);
if((numDigits &1) != 0){
num = calChefora(L);
for(long i = L+1 ; i <= R ; i++){
temp = temp + calChefora(i);
}
sol = modPow(num , temp) ;
System.out.println(sol);
}
}

}

static int countDigit(long n)
{
return (int)Math.floor(Math.log10(n) + 1);
}
static long calChefora(long num){
String temp = Long.toString(num);
if(num%10 == num)return num;
num = num / 10;
long reversed = 0;
while(num!=0){
reversed = reversed * 10 +  num % 10;
num /= 10;
}
temp = temp + reversed;
long sol = Long.parseLong(temp);
return sol;

}

static long modPow(long var, long num) {
long m = 1;long M = 1000000007;
while (num > 0) {
m = (m * var) % M;
--num;
}
return m;
}
}



Modified Code

class CHEFORA
{

StringTokenizer st;
}
String next(){
while(st == null || !st.hasMoreElements()){
try{
}catch(Exception e){
System.out.println(e);
}
}
return st.nextToken();
}
public long nextLong(){
return Long.parseLong(next());
}
public int nextInt(){
return Integer.parseInt(next());
}
}
public static void main (String[] args) throws java.lang.Exception
{

int Q = fr.nextInt();
ArrayList<Long> arrL = new ArrayList();
ArrayList<Long> arrR = new ArrayList();
ArrayList<Long> chefora = new ArrayList();

for(int i = 0 ; i < Q ; i++){

long L = fr.nextLong();
long R = fr.nextLong();

}
for(long i = Collections.min(arrL) ; i <= Collections.max(arrR) ; i++){
long temp = 0;
temp = temp + calChefora(i);
}
for(int i = 0 ; i < Q ; i++){
long num = 0;long sol = 0;
int numDigits = countDigit(arrL.get(i));

if((numDigits &1) != 0) {
long temp = 0;
num = calChefora(arrL.get(i));
int indexL = chefora.indexOf(num);
indexL +=1;
long diff = arrR.get(i) - arrL.get(i);

while(diff-->0){
temp = temp + chefora.get(indexL);
indexL++;
}

sol = modPow(num, temp);
}
System.out.println(sol);
}
}

static int countDigit(long n)
{
return (int)Math.floor(Math.log10(n) + 1);
}
static long calChefora(long num){
if(num%10 == num)return num;
String input =  String.valueOf(num);
StringBuilder input1 = new StringBuilder();
input1.append(input);
input1.reverse();
String tsol = input;
for(int i = 1 ; i < input1.length() ;i++ ){
tsol = tsol  + input1.charAt(i);
}
long sol = Long.parseLong(tsol);
return sol;

}
static long modPow(long x, long y)
{
long M = 1000000007;
long res = 1;

x = x % M;

if (x == 0)
return 0;

while (y > 0)
{

if ((y & 1) != 0)
res = (res * x) % M;

y = y >> 1; // y = y/2
x = (x * x) % M;
}
return res;
}

}

• Check this: geeksforgeeks.org/… Jul 6, 2021 at 15:02
• I tried this but now I am getting WA(Wrong Answer) while submitting but for the given test cases its showing correct answer. I have Added the Modified Code in the Question Jul 8, 2021 at 5:44

First of all, kudos for figuring out that $$\\displaystyle \prod _{i=L+1}^{R} (A_{L})^{ A_{i}} = A_L^{\sum_{i = L+1}^R A_i}\$$.

But - you've stopped too early. The next step is to realize that

$$\\displaystyle \sum_{i = L+1}^R A_i = \sum_{i = 0}^R A_i - \sum_{i = 0}^L A_i\$$

which hints that you need to deal with partial sums of $$\A_i\$$. This way you don't have to recompute the same Chefora numbers over and over again (which you do).

That said, calChefora seems suboptimal. A simple reversal of temp avoids all those modulos, divisions and multiplications.

As noted in comments, exponentiation by squaring is much faster than a naive one. Also, exponentiating modulo prime hints that Fermat's Little may help.

Finally, I failed to understand the (numDigits & 1) != 0 test. Why parity of digits in L is important?

• In the Question its stated that the digits should be of odd length thats why (numDigits & 1) != 0 . Also i have tried changing my code and now I am first taking all the values of L and M and then I am calculating the chefora numbers from the least L to max M so that I dont have to calculate the chefora number again and again and thus reducing my time complexity but still I am getting TLE(Time limit Exceeded when submitting). Also for calculating modPow I have used bit manipulation instead of the regular calculation but still nothing. Jul 8, 2021 at 5:24
• I have added the same in the Question under Modified Code Jul 8, 2021 at 5:29