2
\$\begingroup\$

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 11 

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

}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Check this: geeksforgeeks.org/… \$\endgroup\$ Jul 6, 2021 at 15:02
  • \$\begingroup\$ 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 \$\endgroup\$
    – Saurav
    Jul 8, 2021 at 5:44

1 Answer 1

1
\$\begingroup\$

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?

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Saurav
    Jul 8, 2021 at 5:24
  • \$\begingroup\$ I have added the same in the Question under Modified Code \$\endgroup\$
    – Saurav
    Jul 8, 2021 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.