A perfect power is a number that can be expressed as power of another positive integer.
Given a number n, find count of numbers from 1 to n that are of type xy where x >= 1 and y > 1
Examples :
Input : n = 10 Output : 4 1 4 8 and 9 are the numbers that are of form x ^ y where x > 0 and y > 1 Input : n = 50 Output : 10
A simple solution is to go through all powers of numbers from i = 2 to square root of n.
C++
// CPP program to count number of numbers from// 1 to n are of type x^y where x>0 and y>1#include <bits/stdc++.h>using namespace std;// For our convenience#define ll long long// Function that keeps all the odd power// numbers upto nint powerNumbers(int n){ // v is going to store all power numbers vector<int> v; v.push_back(1); // Traverse through all base numbers and // compute all their powers smaller than // or equal to n. for (ll i = 2; i * i <= n; i++) { ll j = i * i; v.push_back(j); while (j * i <= n) { v.push_back(j * i); j = j * i; } } // Remove all duplicates sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v.size();}int main(){ cout << powerNumbers(50); return 0;} |
Java
// Java program to count number of numbers from// 1 to n are of type x^y where x>0 and y>1import java.io.*;import java.util.*;public class GFG { // Function that keeps all the odd power // numbers upto n static int powerNumbers(int n) { // v is going to store all unique // power numbers HashSet<Integer> v = new HashSet<Integer>(); v.add(1); // Traverse through all base numbers // and compute all their powers // smaller than or equal to n. for (int i = 2; i * i <= n; i++) { int j = i * i; v.add(j); while (j * i <= n) { v.add(j * i); j = j * i; } } return v.size(); } // Driver code public static void main(String args[]) { System.out.print(powerNumbers(50)); }} // This code is contributed by Manish Shaw// (manishshaw1) |
Python3
# Python3 program to count number # of numbers from 1 to n are of# type x^y where x>0 and y>1# Function that keeps all the odd# power numbers upto ndef powerNumbers(n): # v is going to store all # unique power numbers v = set(); v.add(1); # Traverse through all base # numbers and compute all # their powers smaller than # or equal to n. for i in range(2, n+1): if(i * i <= n): j = i * i; v.add(j); while (j * i <= n): v.add(j * i); j = j * i; return len(v); print (powerNumbers(50));# This code is contributed by # Manish Shaw (manishshaw1) |
C#
// C# program to count number of numbers from// 1 to n are of type x^y where x>0 and y>1using System;using System.Collections.Generic;using System.Linq;class GFG { // Function that keeps all the odd power // numbers upto n static int powerNumbers(int n) { // v is going to store all unique // power numbers HashSet<int> v = new HashSet<int>(); v.Add(1); // Traverse through all base numbers // and compute all their powers // smaller than or equal to n. for (int i = 2; i * i <= n; i++) { int j = i * i; v.Add(j); while (j * i <= n) { v.Add(j * i); j = j * i; } } return v.Count; } // Driver code public static void Main() { Console.WriteLine(powerNumbers(50)); }}// This code is contributed by Manish Shaw// (manishshaw1) |
PHP
<?php// PHP program to count number of// numbers from 1 to n are of type// x^y where x>0 and y>1// Function that keeps all the // odd power numbers upto nfunction powerNumbers($n){ // v is going to store // all power numbers $v = array(); array_push($v, 1); // Traverse through all base // numbers and compute all // their powers smaller than // or equal to n. for ($i = 2; $i * $i <= $n; $i++) { $j = $i * $i; array_push($v, $j); while ($j * $i <= $n) { array_push($v, $j * $i); $j = $j * $i; } } // Remove all duplicates sort($v); $v = array_unique($v); return count($v);}// Driver Codeecho (powerNumbers(50));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script> // JavaScript program to count number of numbers from // 1 to n are of type x^y where x>0 and y>1 // Function that keeps all the odd power // numbers upto n function powerNumbers(n) { // v is going to store all unique // power numbers let v = new Set(); v.add(1); // Traverse through all base numbers // and compute all their powers // smaller than or equal to n. for (let i = 2; i * i <= n; i++) { let j = i * i; v.add(j); while (j * i <= n) { v.add(j * i); j = j * i; } } return v.size; } document.write(powerNumbers(50));</script> |
Output:
10
Time Complexity: O(nlogn)
Auxiliary Space: O(n)
Efficient Solution
We divide output set into subsets.
Even Powers: Simply we need to square root n. The count of even powers smaller than n is square root of n. For example even powers smaller than 25 are (1, 4, 9, 16 and 25).
Odd Powers: We modify above function to consider only odd powers.
C++
// C++ program to count number of numbers from// 1 to n are of type x^y where x>0 and y>1#include <bits/stdc++.h>using namespace std;// For our convenience#define ll long long// Function that keeps all the odd power// numbers upto nint powerNumbers(int n){ vector<int> v; for (ll i = 2; i * i * i <= n; i++) { ll j = i * i; while (j * i <= n) { j *= i; // We need exclude perfect // squares. ll s = sqrt(j); if (s * s != j) v.push_back(j); } } // sort the vector sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); // Return sum of odd and even powers. return v.size() + (ll)sqrt(n);}int main(){ cout << powerNumbers(50); return 0;} |
Java
// Java program to count number // of numbers from 1 to n are// of type x^y where x>0 and y>1import java.io.*;import java.util.*;class GFG{ // Function that keeps all // the odd power numbers upto n static long powerNumbers(int n) { HashSet<Long> v = new HashSet<Long>(); for (long i = 2; i * i * i <= n; i++) { long j = i * i; while (j * i <= n) { j *= i; // We need exclude // perfect squares. long s = (long)Math.sqrt(j); if (s * s != j) v.add(j); } } // sort the vector // v.Sort(); // v.erase(unique(v.begin(), // v.end()), v.end()); // Return sum of odd // and even powers. return v.size() + (long)Math.sqrt(n); } // Driver Code public static void main(String args[]) { System.out.print(powerNumbers(50)); }}// This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Python3 program to count number of # numbers from 1 to n are of type x^y# where x>0 and y>1import math # Function that keeps all the odd power# numbers upto ndef powerNumbers( n): v = [] for i in range(2, int(math.pow(n, 1.0 / 3.0)) + 1) : j = i * i while (j * i <= n) : j = j * i # We need exclude perfect # squares. s = int(math.sqrt(j)) if (s * s != j): v.append(j) # sort the vector v.sort() v = list(dict.fromkeys(v)) # Return sum of odd and even powers. return len(v) + int(math.sqrt(n))# Driver Codeif __name__=='__main__': print (powerNumbers(50)) # This code is contributed by Arnab Kundu |
C#
// C# program to count number // of numbers from 1 to n are// of type x^y where x>0 and y>1using System;using System.Collections.Generic;class GFG{ // Function that keeps all // the odd power numbers upto n static long powerNumbers(int n) { HashSet<long> v = new HashSet<long>(); for (long i = 2; i * i * i <= n; i++) { long j = i * i; while (j * i <= n) { j *= i; // We need exclude // perfect squares. long s = (long)Math.Sqrt(j); if (s * s != j) v.Add(j); } } // sort the vector //v.Sort(); //v.erase(unique(v.begin(), // v.end()), v.end()); // Return sum of odd // and even powers. return v.Count + (long)Math.Sqrt(n); } // Driver Code static void Main() { Console.Write(powerNumbers(50)); }}// This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php// PHP program to count number // of numbers from 1 to n are// of type x^y where x>0 and y>1// Function that keeps all the// odd power numbers upto nfunction powerNumbers($n){ $v = array(); for ($i = 2; $i * $i * $i <= $n; $i++) { $j = $i * $i; while ($j * $i <= $n) { $j *= $i; // We need exclude perfect // squares. $s = sqrt($j); if ($s * $s != $j) array_push($v, $j); } } // sort the vector sort($v); $uni = array_unique($v); for ($i = 0; $i < count($uni); $i++) { $key = array_search($uni[$i], $v); unset($v[$key]); } // Return sum of odd // and even powers. return count($v) + 3 + intval(sqrt($n));}// Driver Codeecho (powerNumbers(50));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script> // Javascript program to count number // of numbers from 1 to n are // of type x^y where x>0 and y>1 // Function that keeps all // the odd power numbers upto n function powerNumbers(n) { let v = new Set(); for (let i = 2; i * i * i <= n; i++) { let j = i * i; while (j * i <= n) { j *= i; // We need exclude // perfect squares. let s = parseInt(Math.sqrt(j), 10); if (s * s != j) v.add(j); } } // sort the vector // v.Sort(); // v.erase(unique(v.begin(), // v.end()), v.end()); // Return sum of odd // and even powers. return v.size + parseInt(Math.sqrt(n), 10); } document.write(powerNumbers(50));// This code is contributed by vaibhavrabadiya3.</script> |
Output :
10
Time Complexity: O(nlogn)
Auxiliary Space: O(n^(1/4))
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!
