Given an array Q[][] consisting of N queries of the form {L, R}, the task for each query is to find the total count of numbers from the range [L, R], whose cube is a palindrome.
Examples:
Input: Q[][] = {{2, 10}, {10, 20}}
Output:
2
1
Explanation:
Query 1: The numbers from the range [2, 10], whose cube is a palindrome are 2, 7
Query 2: The only number from the range [10, 20], whose cube is a palindrome is 11Input: Q[][] = {{1, 50}, {13, 15}}
Output:
4
0
Explanation:
Query 1: The numbers from the range [1, 50], whose cube is a palindrome are {1, 2, 7, 11}.
Query 2: No such number exists in the range [13, 15].
Approach: The simplest idea to solve the problem is to use Inclusion-Exclusion Principle and Prefix Sum Array technique to solve this problem. Follow the steps below to solve the given problem:
- Initialize an array arr[], to store at every ith index, whether cube of i is a palindrome or not.
- Traverse the array arr[] and for every ith index, check if the cube of i is a palindrome or not.
- If found to be true, then set arr[i] = 1.
- Otherwise, set arr[i] = 0.
- Convert the array arr[] to a prefix sum array.
- Traverse the array Q[][], and count the number from the range [L, R] whose cube is a palindrome by calculating arr[R] – arr[L-1].
Below is the implementation of the above approach.
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;int arr[10005];// Function to check if n is// a palindrome number or notint isPalindrome(int n){ // Temporarily store n int temp = n; // Stores reverse of n int res = 0; // Iterate until temp reduces to 0 while (temp != 0) { // Extract the last digit int rem = temp % 10; // Add to the start res = res * 10 + rem; // Remove the last digit temp /= 10; } // If the number and its // reverse are equal if (res == n) { return 1; } // Otherwise else return 0;}// Function to precompute and store// the count of numbers whose cube// is a palindrome numbervoid precompute(){ // Iterate upto 10^4 for (int i = 1; i <= 10000; i++) { // Check if i*i*i is a // palindrome or not if (isPalindrome(i * i * i)) arr[i] = 1; else arr[i] = 0; } // Convert arr[] to prefix sum array for (int i = 1; i <= 10000; i++) { arr[i] = arr[i] + arr[i - 1]; }}// Driver Codeint main(){ // Given queries vector<pair<int, int> > Q = { { 2, 7 }, { 10, 25 } }; precompute(); for (auto it : Q) { // Using inclusion-exclusion // principle, count required numbers cout << arr[it.second] - arr[it.first - 1] << "\n"; } return 0;} |
Java
// Java program of the above approachimport java.io.*;import java.util.*;public class Pair { private final int key; private final int value; public Pair(int aKey, int aValue) { key = aKey; value = aValue; } public int key() { return key; } public int value() { return value; }}class GFG { static int[] arr = new int[10005]; // Function to check if n is // a palindrome number or not static int isPalindrome(int n) { // Temporarily store n int temp = n; // Stores reverse of n int res = 0; // Iterate until temp reduces to 0 while (temp != 0) { // Extract the last digit int rem = temp % 10; // Add to the start res = res * 10 + rem; // Remove the last digit temp /= 10; } // If the number and its // reverse are equal if (res == n) { return 1; } // Otherwise else return 0; } // Function to precompute and store // the count of numbers whose cube // is a palindrome number static void precompute() { // Iterate upto 10^4 for (int i = 1; i <= 10000; i++) { // Check if i*i*i is a // palindrome or not if (isPalindrome(i * i * i)!= 0) arr[i] = 1; else arr[i] = 0; } // Convert arr[] to prefix sum array for (int i = 1; i <= 10000; i++) { arr[i] = arr[i] + arr[i - 1]; } } // Driver Code public static void main(String[] args) { // Given queries ArrayList<Pair> Q = new ArrayList<Pair>(); Pair pair = new Pair(2, 7); Q.add(pair); Pair pair2 = new Pair(10, 25); Q.add(pair2); precompute(); for (int i = 0; i < Q.size(); i++) { // Using inclusion-exclusion // principle, count required numbers System.out.println(arr[Q.get(i).value()] - arr[Q.get(i).key()-1]); } }}// This code is contributed by Dharanendra L V |
Python3
# Python program of the above approacharr = [0] * 10005# Function to check if n is# a palindrome number or notdef isPalindrome(n): # Temporarily store n temp = n # Stores reverse of n res = 0 # Iterate until temp reduces to 0 while temp != 0: # Extract the last digit rem = temp % 10 # Add to the start res = res * 10 + rem # Remove the last digit temp = temp // 10 # If the number and its # reverse are equal if res == n: return 1 # Otherwise else: return 0# Function to precompute and store# the count of numbers whose cube# is a palindrome numberdef precompute(): # Iterate upto 10^4 for i in range(1, 10001): # Check if i*i*i is a # palindrome or not if isPalindrome(i * i * i): arr[i] = 1 else: arr[i] = 0 # Convert arr[] to prefix sum array for i in range(1, 10001): arr[i] = arr[i] + arr[i - 1]# Given queriesQ = [[2, 7], [10, 25]]precompute()for it in Q: # Using inclusion-exclusion # principle, count required numbers print(arr[it[1]] - arr[it[0] - 1])# This code is implemented by Phasing17 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class Pair { private readonly int key; private readonly int value; public Pair(int aKey, int aValue) { key = aKey; value = aValue; } public int Key() { return key; } public int Value() { return value; }}class GFG { static int[] arr = new int[10005]; // Function to check if n is // a palindrome number or not static int IsPalindrome(int n) { // Temporarily store n int temp = n; // Stores reverse of n int res = 0; // Iterate until temp reduces to 0 while (temp != 0) { // Extract the last digit int rem = temp % 10; // Add to the start res = res * 10 + rem; // Remove the last digit temp /= 10; } // If the number and its // reverse are equal if (res == n) { return 1; } // Otherwise else { return 0; } } // Function to precompute and store // the count of numbers whose cube // is a palindrome number static void Precompute() { // Iterate upto 10^4 for (int i = 1; i <= 10000; i++) { // Check if i*i*i is a // palindrome or not if (IsPalindrome(i * i * i) != 0) { arr[i] = 1; } else { arr[i] = 0; } } // Convert arr[] to prefix sum array for (int i = 1; i <= 10000; i++) { arr[i] = arr[i] + arr[i - 1]; } } // Driver Code static void Main() { // Given queries var Q = new List<Pair> { new Pair(2, 7), new Pair(10, 25) }; Precompute(); for (int i = 0; i < Q.Count; i++) { // Using inclusion-exclusion // principle, count required numbers Console.WriteLine(arr[Q[i].Value()] - arr[Q[i].Key() - 1]); } }}// This code is contributed by phasing17 |
Javascript
<script>// Javascript program of the above approachlet arr = new Array(10005).fill(0)// Function to check if n is// a palindrome number or notfunction isPalindrome(n) { // Temporarily store n let temp = n; // Stores reverse of n let res = 0; // Iterate until temp reduces to 0 while (temp != 0) { // Extract the last digit let rem = temp % 10; // Add to the start res = res * 10 + rem; // Remove the last digit temp = Math.floor(temp / 10); } // If the number and its // reverse are equal if (res == n) { return 1; } // Otherwise else return 0;}// Function to precompute and store// the count of numbers whose cube// is a palindrome numberfunction precompute() { // Iterate upto 10^4 for (let i = 1; i <= 10000; i++) { // Check if i*i*i is a // palindrome or not if (isPalindrome(i * i * i)) arr[i] = 1; else arr[i] = 0; } // Convert arr[] to prefix sum array for (let i = 1; i <= 10000; i++) { arr[i] = arr[i] + arr[i - 1]; }}// Driver Code// Given querieslet Q = [[2, 7], [10, 25]];precompute();for (let it of Q) { // Using inclusion-exclusion // principle, count required numbers document.write(arr[it[1]] - arr[it[0] - 1] + "<br>");}// This code is contributed by saurabh_jaiswal.</script> |
Output:
2 1
Time Complexity: O(N)
Auxiliary Space: O(maxm), where maxm denotes the maximum value of R in a query
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
