Chef vs Bharat | CodeChef Solution

Hello coders, today we are going to solve Chef vs Bharat CodeChef Solution whose Problem Code is CHEFORA.

Task

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
where N_i is the i-th digit of N from the left in 0-based indexing.

Let A_i denote the i-th largest 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

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 ≤ N, Q ≤ 10⁵
• 1 ≤ L < R ≤ N

Subtasks

Subtask #1 (30 points): 1 ≤ N, Q ≤ 5⋅10³
Subtask #2 (70 points): Original constraints

Sample Input

2
1 2
9 11

Sample Output

1
541416750

Explanation

• For the first question:
• (A¹)^A₂ = 1² = 1.
• For the second question:
• (A⁹)^A₁₀ ⋅ (A⁹)^A₁₁ = 9¹⁰¹ ⋅ 9¹¹¹ ≡ 541416750 (mod 10⁹+7).

Solution – Chef vs Bharat

C++

class PalindromeAndPrefixSumEncapsulated:
  def __init__(self, n):
    self.n = n
    self.i = 0
    self.palindromes = [0]*n
    self.prefixSums = [0]*n
   
  def add(self, val):
    self.palindromes[self.i] = val
    self.prefixSums[self.i] = val
    if self.i != 0:
      self.prefixSums[self.i] += self.prefixSums[self.i-1]
    self.i = self.i+1
   
  def isFull(self):
    return self.i == self.n
       
  def getPrefixSumInRange(self, L, R):
    return self.prefixSums[R]-self.prefixSums[L]
       
  def getFirstPalin(self, index):
    return self.palindromes[index]
 
     
def createOddPalin(inp):
  n = inp
  palin = inp
  n = n//10
  while n > 0:
    palin = palin*10+(n%10)
    n = n//10
  return palin;
 
 
def generatePalindromes(palindromeAndPrefixSumEncapsulated):
  i = 1
  while not palindromeAndPrefixSumEncapsulated.isFull():
    palindromeAndPrefixSumEncapsulated.add(createOddPalin(i))
    i = i+1
   
 
def solve(L, R, palindromeAndPrefixSumEncapsulated):
    power = palindromeAndPrefixSumEncapsulated.getPrefixSumInRange(L-1, R-1);
    base = palindromeAndPrefixSumEncapsulated.getFirstPalin(L-1);
    return pow(base, power, 1000000007);
 
palindromeAndPrefixSumEncapsulated = PalindromeAndPrefixSumEncapsulated(100001)
generatePalindromes(palindromeAndPrefixSumEncapsulated)
q = int(input())
while q > 0:
    q = q-1
    line = input().split(" ")
    L, R = int(line[0]), int(line[1])
    print(solve(L, R, palindromeAndPrefixSumEncapsulated))
    
    

Python

# cook your dish here
def odd_Palindrome(val):
	n, palindrome = val, val
	n //= 10
	while n > 0:
		palindrome = ((palindrome * 10) + (n % 10))
		n //= 10
	return palindrome

class Palin():
	"""docstring for Palin"""
	def __init__(self, n):
		super(Palin, self).__init__()
		self.n = n
		self.i = 0
		self.palindrome = [0]*n
		self.prefix = [0]*n

	def fill(self):
		return self.i == self.n
	def add(self, v):
		self.palindrome[self.i] = v
		self.prefix[self.i] = v
		if self.i != 0:
			self.prefix[self.i] += self.prefix[self.i - 1]
		self.i = self.i + 1
	
	def basePalin(self, l):
		return self.palindrome[l]
		
	def rangedPrefix(self, l, r):
		return self.prefix[r] - self.prefix[l]

def create_Palin(palindrome):
	idx = 1
	while not palindrome.fill():
		palindrome.add(odd_Palindrome(idx))
		idx += 1

def calc(left, right, palindrome):
	power = palindrome.rangedPrefix(left - 1, right - 1)
	base = palindrome.basePalin(left - 1)
	return pow(base, power, 1000000007)

class Solution(object):
	try:
		obj_Palin = Palin(100001)
		create_Palin(obj_Palin)

		num_Of_Queries = int(input())
		while num_Of_Queries > 0:
			left, right = map(int, input().split( ))
			print(calc(left, right, obj_Palin))
			num_Of_Queries -= 1

	except Exception as e:
		raise e

Java

/* package codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    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 (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) throws java.lang.Exception {
        // your code goes here
        long[] preComputedArray = new long[100001];
        long[] computedDifferenceArray = new long[100001];
        // System.out.println("reverse" + reverseNum(25963));
        for (int j = 1; j < preComputedArray.length; j++) {

            preComputedArray[j] = reverseNum(j);
            computedDifferenceArray[j] = preComputedArray[j] + computedDifferenceArray[j - 1];
            // System.out.println("reverseNum: " + reverseNum(j));
        }
        // System.out.println(Arrays.toString(preComputedArray));
        // System.out.println("Dffernce");
        // System.out.println(Arrays.toString(preComputedDifferenceArray));
        FastReader sc = new FastReader();
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        long mod = 1000000007;
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            long diff = computedDifferenceArray[r] - computedDifferenceArray[l];
            long ans  =  (power(preComputedArray[l], diff, mod)) % mod;


            out.write(ans + "\n");
        }
        out.flush();
    }

    // Utility function to reverse the number n
    static long reverseNum(long n) {
        long newN = n;
        long rem, rev = 0;
        n = n / 10;
        while (n > 0) {
            rem = n % 10;
            newN = newN * 10 + rem;
            n /= 10;
        }
        rev = newN;
        return rev;
    }

    // Boolean Function to check for palindromic
    // number
    static boolean isPalindrom(int num) {
        return num == reverseNum(num);
    }

    // Function for finding nth palindrome of k digits
    static int nthPalindrome(int n, int k) {
        // Get the smallest k digit number
        int num = (int) Math.pow(10, k - 1);

        while (true) {
            // check the number is palindrom or not
            if (isPalindrom(num))
                --n;

            // if n'th palindrome found break the loop
            if (n == 0)
                break;

            // Increment number for checking next palindrome
            ++num;
        }

        return num;
    }

    static int printPalindromes(int d, long[] arr, int indexTrack) {
        if (d <= 0)
            return 0;

        // Smallest and the largest d-digit numbers
        int smallest = (int) Math.pow(10, d - 1);
        int largest = (int) Math.pow(10, d) - 1;

        // Starting from the smallest d-digit
        // number till the largest
        for (int i = smallest; i <= largest; i++) {
            // If the current number
            // is palindrome
            if (isPalindrom(i)) {
                arr[indexTrack++] = i;
                // System.out.print(i + " ");
            }
        }
        return indexTrack;
    }

    static long power(long x, long y, long mod) {
        long res = 1; // Initialize result
        x = x % mod;
        if (x == 0) {
            return 0;
        }
        while (y > 0) {

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

            y = y >> 1;
            x = (x * x) % mod;

        }
        return res%mod;
    }


}

Disclaimer: The above Problem (Chef vs Bharat) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.