Given a number n, the task is to print all the numbers less than or equal to n which are perfect cubes as well as the eventual sum of their digits is 1.
Examples:
Input: n = 100
Output: 1 64
64 = 6 + 4 = 10 = 1 + 0 = 1
Input: n = 1000
Output: 1 64 343 1000
Approach: For every perfect cube less than or equal to n keep on calculating the sum of its digits until the number is reduced to a single digit ( O(1) approach here ), if this digit is 1 then print the perfect cube else skip to the next perfect cube below n until all the perfect cubes have been considered.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <cmath>#include <iostream>using namespace std;// Function that returns true if the eventual// digit sum of number nm is 1bool isDigitSumOne(int nm){ //if reminder will 1 //then eventual sum is 1 if (nm % 9 == 1) return true; else return false;}// Function to print the required numbers// less than nvoid printValidNums(int n){ int cbrt_n = (int)cbrt(n); for (int i = 1; i <= cbrt_n; i++) { int cube = pow(i, 3); // If it is the required perfect cube if (cube >= 1 && cube <= n && isDigitSumOne(cube)) cout << cube << " "; }}// Driver codeint main(){ int n = 1000; printValidNums(n); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function that returns true if the eventual // digit sum of number nm is 1 static boolean isDigitSumOne(int nm) { //if reminder will 1 //then eventual sum is 1 if (nm % 9 == 1) return true; else return false; } // Function to print the required numbers // less than n static void printValidNums(int n) { int cbrt_n = (int)Math.cbrt(n); for (int i = 1; i <= cbrt_n; i++) { int cube = (int)Math.pow(i, 3); // If it is the required perfect cube if (cube >= 1 && cube <= n && isDigitSumOne(cube)) System.out.print(cube + " "); } } // Driver code public static void main(String args[]) { int n = 1000; printValidNums(n); }} |
Python
# Python3 implementation of the approachimport math# Function that returns true if the eventual # digit sum of number nm is 1def isDigitSumOne(nm) : #if reminder will 1 #then eventual sum is 1 if(nm % 9 == 1): return True else: return False# Function to print the required numbers# less than ndef printValidNums(n): cbrt_n = math.ceil(n**(1./3.)) for i in range(1, cbrt_n + 1): cube = i * i * i if (cube >= 1 and cube <= n and isDigitSumOne(cube)): print(cube, end = " ") # Driver code n = 1000printValidNums(n) |
C#
// C# implementation of the approachusing System;class GFG{ // Function that returns true if the // eventual digit sum of number nm is 1 static bool isDigitSumOne(int nm) { //if reminder will 1 //then eventual sum is 1 if (nm % 9 == 1) return true; else return false; } // Function to print the required // numbers less than n static void printValidNums(int n) { int cbrt_n = (int)Math.Ceiling(Math.Pow(n, (double) 1 / 3)); for (int i = 1; i <= cbrt_n; i++) { int cube = (int)Math.Pow(i, 3); // If it is the required perfect cube if (cube >= 1 && cube <= n && isDigitSumOne(cube)) Console.Write(cube + " "); } } // Driver code static public void Main () { int n = 1000; printValidNums(n); }}// This code is contributed by akt_mit |
PHP
<?php// PHP implementation of the approach // Function that returns true if the // eventual digit sum of number nm is 1 function isDigitSumOne($nm) { //if reminder will 1 //then eventual sum is 1 if ($nm % 9 == 1) return true; else return false; } // Function to print the required numbers // less than n function printValidNums($n) { $cbrt_n = ceil(pow($n,1/3)); for ($i = 1; $i <= $cbrt_n; $i++) { $cube = pow($i, 3); // If it is the required perfect cube if ($cube >= 1 && $cube <= $n && isDigitSumOne($cube)) echo $cube, " "; } } // Driver code $n = 1000; printValidNums($n); // This code is contributed by Ryuga?> |
Javascript
<script> // Javascript implementation of the approach // Function that returns true if the // eventual digit sum of number nm is 1 function isDigitSumOne(nm) { //if reminder will 1 //then eventual sum is 1 if (nm % 9 == 1) return true; else return false; } // Function to print the required // numbers less than n function printValidNums(n) { let cbrt_n = Math.ceil(Math.pow(n, 1 / 3)); for (let i = 1; i <= cbrt_n; i++) { let cube = Math.pow(i, 3); // If it is the required perfect cube if (cube >= 1 && cube <= n && isDigitSumOne(cube)) document.write(cube + " "); } } let n = 1000; printValidNums(n); </script> |
Output:
1 64 343 1000
Time Complexity: O(cbrt(n))
Auxiliary Space: O(1)
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!
