Given a range [L, R], the task is to find the count of numbers in the range [L, R] that can be expressed as a sum of two perfect powers.
Examples:
Input: L = 0, R = 1
Output: 2
Explanation:
The valid numbers are:
- 1 as it can be expressed as, 1 = 12 + 02.
- 0 as it can be expressed as, 0 = 02 + 02.
Therefore, the count of such numbers is 2.
Input: L = 5, R = 8
Output: 2
Explanation:
The valid numbers are:
- 5 as it can be expressed as, 5 = 12 + 22.
- 8 as it can be expressed as, 0 = 02 + 23.
Therefore, the count of such numbers is 2.
Approach: The given problem can be solved by using some mathematical observations. Follow the steps below to solve the problem:
- Generate all possible power of all the numbers that are less than R from 2 and store those numbers in an array pow[].
- Initialize a boolean array, say arr[] of size (R + 1) as 0.
- Generate all possible distinct pairs of the array pow[] and if the sum of pairs is at most R then mark it as 1 in the array arr[].
- Now, find the prefix sum of the array arr[].
- After completing the above steps, print the value of arr[R] – arr[L – 1] as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of numbers// that can be expressed in the form of// the sum of two perfect powersint TotalPerfectPowerSum(long long L, long long R){ // Stores all possible powers vector<long long> pows; // Push 1 and 0 in it pows.push_back(0); pows.push_back(1); // Iterate over all the exponents for (int p = 2; p < 25; p++) { // Iterate over all possible numbers long long int num = 2; // This loop will run for a // maximum of sqrt(R) times while ((long long int)(pow(num, p) + 0.5) <= R) { // Push this power in // the array pows[] pows.push_back( (long long int)(pow(num, p) + 0.5)); // Increase the number num++; } } // Stores if i can be expressed as // the sum of perfect power or not int ok[R + 1]; memset(ok, 0, sizeof(ok)); // Iterate over all possible pairs // of the array pows[] for (int i = 0; i < pows.size(); i++) { for (int j = 0; j < pows.size(); j++) { if (pows[i] + pows[j] <= R and pows[i] + pows[j] >= L) { // The number is valid ok[pows[i] + pows[j]] = 1; } } } // Find the prefix sum of the // array ok[] for (int i = 0; i <= R; i++) { ok[i] += ok[i - 1]; } // Return the count of required number return ok[R] - ok[L - 1];}// Driver Codesigned main(){ int L = 5, R = 8; cout << TotalPerfectPowerSum(L, R); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the number of numbers // that can be expressed in the form of // the sum of two perfect powers static int TotalPerfectPowerSum(int L, int R) { // Stores all possible powers ArrayList<Integer> pows = new ArrayList<Integer>(); // Push 1 and 0 in it pows.add(0); pows.add(1); // Iterate over all the exponents for (int p = 2; p < 25; p++) { // Iterate over all possible numbers int num = 2; // This loop will run for a // maximum of sqrt(R) times while ((int)(Math.pow(num, p) + 0.5) <= R) { // Push this power in // the array pows[] pows.add((int)(Math.pow(num, p) + 0.5)); // Increase the number num++; } } // Stores if i can be expressed as // the sum of perfect power or not int[] ok = new int[R + 2]; // memset(ok, 0, sizeof(ok)); // Iterate over all possible pairs // of the array pows[] for (int i = 0; i < pows.size(); i++) { for (int j = 0; j < pows.size(); j++) { if (pows.get(i) + pows.get(j) <= R && pows.get(i) + pows.get(j) >= L) { // The number is valid ok[pows.get(i) + pows.get(j)] = 1; } } } // Find the prefix sum of the // array ok[] for (int i = 1; i <= R; i++) { ok[i] += ok[i - 1]; } // Return the count of required number return ok[R] - ok[L - 1]; } // Driver Code public static void main(String args[]) { int L = 5, R = 8; System.out.print(TotalPerfectPowerSum(L, R)); }}// This code is contributed by avijitmondal1998. |
Python3
# python program for the above approach# Function to find the number of numbers# that can be expressed in the form of# the sum of two perfect powersdef TotalPerfectPowerSum(L, R): # Stores all possible powers pows = [] # Push 1 and 0 in it pows.append(0) pows.append(1) # Iterate over all the exponents for p in range(2, 25): # Iterate over all possible numbers num = 2 # This loop will run for a # maximum of sqrt(R) times while ((int)(pow(num, p) + 0.5) <= R): # Push this power in # the array pows[] pows.append((int)(pow(num, p) + 0.5)) # Increase the number num = num + 1 # Stores if i can be expressed as # the sum of perfect power or not ok = [0 for _ in range(R + 1)] # int ok[R + 1]; # memset(ok, 0, sizeof(ok)); # Iterate over all possible pairs # of the array pows[] for i in range(0, int(len(pows))): for j in range(0, len(pows)): if (pows[i] + pows[j] <= R and pows[i] + pows[j] >= L): # The number is valid ok[pows[i] + pows[j]] = 1 # Find the prefix sum of the # array ok[] for i in range(0, R+1): ok[i] += ok[i - 1] # Return the count of required number return ok[R] - ok[L - 1]# Driver Codeif __name__ == "__main__": L = 5 R = 8 print(TotalPerfectPowerSum(L, R)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the number of numbers // that can be expressed in the form of // the sum of two perfect powers static int TotalPerfectPowerSum(long L, long R) { // Stores all possible powers List<long> pows = new List<long>(); // Push 1 and 0 in it pows.Add(0); pows.Add(1); // Iterate over all the exponents for (int p = 2; p < 25; p++) { // Iterate over all possible numbers long num = 2; // This loop will run for a // maximum of sqrt(R) times while ((long)(Math.Pow(num, p) + 0.5) <= R) { // Push this power in // the array pows[] pows.Add((long)(Math.Pow(num, p) + 0.5)); // Increase the number num++; } } // Stores if i can be expressed as // the sum of perfect power or not int[] ok = new int[R + 2]; // memset(ok, 0, sizeof(ok)); // Iterate over all possible pairs // of the array pows[] for (int i = 0; i < pows.Count; i++) { for (int j = 0; j < pows.Count; j++) { if (pows[i] + pows[j] <= R && pows[i] + pows[j] >= L) { // The number is valid ok[pows[i] + pows[j]] = 1; } } } // Find the prefix sum of the // array ok[] for (int i = 1; i <= R; i++) { ok[i] += ok[i - 1]; } // Return the count of required number return ok[R] - ok[L - 1]; } // Driver Code public static void Main() { int L = 5, R = 8; Console.WriteLine(TotalPerfectPowerSum(L, R)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the number of numbers // that can be expressed in the form of // the sum of two perfect powers function TotalPerfectPowerSum(L, R) { // Stores all possible powers let pows = []; // Push 1 and 0 in it pows.push(0); pows.push(1); // Iterate over all the exponents for (let p = 2; p < 25; p++) { // Iterate over all possible numbers let num = 2; // This loop will run for a // maximum of sqrt(R) times while (Math.floor(Math.pow(num, p) + 0.5) <= R) { // Push this power in // the array pows[] pows.push( Math.floor(Math.pow(num, p) + 0.5)); // Increase the number num++; } } // Stores if i can be expressed as // the sum of perfect power or not let ok = new Array(R + 1).fill(0); // Iterate over all possible pairs // of the array pows[] for (let i = 0; i < pows.length; i++) { for (let j = 0; j < pows.length; j++) { if (pows[i] + pows[j] <= R && pows[i] + pows[j] >= L) { // The number is valid ok[pows[i] + pows[j]] = 1; } } } // Find the prefix sum of the // array ok[] for (let i = 1; i <= R; i++) { ok[i] += ok[i - 1]; } // Return the count of required number return ok[R] - ok[L - 1]; } // Driver Code let L = 5, R = 8; document.write(TotalPerfectPowerSum(L, R)); // This code is contributed by Potta Lokesh </script> |
Output:
2
Time Complexity: O(R*log(R))
Auxiliary Space: O(R)
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!
