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<R≤10^5\$
Subtasks
Subtask #1 (30 points):
\$1≤Q≤5⋅10^3\$
\$1≤L<R≤5⋅10^3\$
Subtask #2 (70 points):
Original constraints
Sample Input
2 1 2 9 11Sample Output
1 541416750
Code
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public 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(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
{
// your code goes here
FastReader fr = new FastReader();
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
{
public 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(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
{
// your code goes here
FastReader fr = new FastReader();
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();
arrL.add(L); arrR.add(R);
}
for(long i = Collections.min(arrL) ; i <= Collections.max(arrR) ; i++){
long temp = 0;
temp = temp + calChefora(i);
chefora.add(temp);
}
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;
}
}
