# Chef vs Bharat | CodeChef Solution

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

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

Let Ai 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 ≤ 105
• 1 ≤ L < RN

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

Sample Input

``````2
1 2
9 11``````

Sample Output

``````1
541416750``````

## Explanation

• For the first question:
• (A1)A2 = 12 = 1.
• For the second question:
• (A9)A10 ⋅ (A9)A11 = 9101 ⋅ 9111 ≡ 541416750 (mod 109+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

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():
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
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():
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
{
StringTokenizer st;

}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} 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 {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}

public static void main(String[] args) throws java.lang.Exception {
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));
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.