Finding the Missing digit in the Largest Perfect Cube
Given a perfect cube number with one missing digit represented by an underscore _, the task is to find the missing digit that when inserted, creates the largest perfect cube.
Examples:
Input: “219_”
Output: 7
Explanation: The missing digit 7 makes the largest perfect cube, 2197.Input: 15_25
Output: 6
Explanation: The missing digit 6 makes the largest perfect square, 15625.
Approach: The problem can be solved using the following approach:
Iterate through all possible digits in reverse order (9 to 0) and replace the underscore with the current digit, calculate the cube root of the resulting number, and check if it is a perfect cube. We have iterated in reverse order (9 to 0) because we want to have the largest perfect cube.
Steps to solve the problem:
- Initialize variable missing_digit to -1.
- Iterate through digits from 9 to 0.
- For each digit, replace the underscore in the input number with the current digit.
- Calculate the cube root of the modified number.
- If the cube root is an integer, return the digit.
Below is the implementation of the approach:
C++
#include <cmath> #include <iostream> using namespace std; int findMissingDigitCube(string input_str) { int missing_digit = -1; // Iterate through digits from 9 to 0 for ( int digit = 9; digit >= 0; digit--) { // Replace the underscore with the current digit string modified_str = input_str; size_t pos = modified_str.find( '_' ); if (pos != string::npos) { modified_str.replace(pos, 1, to_string(digit)); } // Calculate the cube root of the modified number double cube_root = cbrt(stoi(modified_str)); // Check if the cube root is an integer if ( abs (round(cube_root) - cube_root) < 1e-9) { missing_digit = digit; break ; } } return missing_digit; } // Driver COde int main() { cout << findMissingDigitCube("219_") << endl; // Output: 7 cout << findMissingDigitCube("15_25") << endl; // Output: 6 return 0; } |
Java
import java.util.regex.Matcher; import java.util.regex.Pattern; public class MissingDigitCube { public static int findMissingDigitCube(String inputStr) { int missingDigit = - 1 ; // Iterate through digits from 9 to 0 for ( int digit = 9 ; digit >= 0 ; digit--) { // Replace the underscore with the current digit String modifiedStr = inputStr.replaceAll( "_" , Integer.toString(digit)); // Calculate the cube root of the modified // number double cubeRoot = Math.cbrt(Integer.parseInt(modifiedStr)); // Check if the cube root is an integer if (Math.abs(Math.round(cubeRoot) - cubeRoot) < 1e- 9 ) { missingDigit = digit; break ; } } return missingDigit; } public static void main(String[] args) { System.out.println( findMissingDigitCube( "219_" )); // Output: 7 System.out.println( findMissingDigitCube( "15_25" )); // Output: 6 } } |
Python3
import math def find_missing_digit_cube(input_str): missing_digit = - 1 # Iterate through digits from 9 to 0 for digit in range ( 9 , - 1 , - 1 ): # Replace the underscore with the current digit modified_str = input_str.replace( '_' , str (digit)) # Calculate the cube root of the modified number cube_root = round ( int (modified_str) * * ( 1 / 3 ), 9 ) # Use rounding to avoid floating-point precision issues # Check if the cube root is an integer if abs (cube_root - round (cube_root)) < 1e - 9 : # Tolerance for floating-point comparison missing_digit = digit break return missing_digit # Driver code print (find_missing_digit_cube(" 219_ ")) # Output: 7 print (find_missing_digit_cube(" 15_25 ")) # Output: 6 |
C#
using System; public class MissingDigitCube { public static int FindMissingDigitCube( string inputStr) { int missingDigit = -1; // Iterate through digits from 9 to 0 for ( int digit = 9; digit >= 0; digit--) { // Replace the underscore with the current digit string modifiedStr = inputStr.Replace( "_" , digit.ToString()); // Calculate the cube root of the modified number double cubeRoot = Math.Cbrt( int .Parse(modifiedStr)); // Check if the cube root is an integer if (Math.Abs(Math.Round(cubeRoot) - cubeRoot) < 1e-9) { missingDigit = digit; break ; } } return missingDigit; } public static void Main( string [] args) { Console.WriteLine(FindMissingDigitCube( "219_" )); // Output: 7 Console.WriteLine(FindMissingDigitCube( "15_25" )); // Output: 6 } } |
Javascript
function findMissingDigitCube(inputStr) { let missingDigit = -1; // Iterate through digits from 9 to 0 for (let digit = 9; digit >= 0; digit--) { // Replace the underscore with the current digit let modifiedStr = inputStr; let pos = modifiedStr.indexOf( '_' ); if (pos !== -1) { modifiedStr = modifiedStr.substring(0, pos) + digit + modifiedStr.substring(pos + 1); } // Calculate the cube root of the modified number let cubeRoot = Math.cbrt(parseInt(modifiedStr)); // Check if the cube root is an integer if (Math.abs(Math.round(cubeRoot) - cubeRoot) < 1e-9) { missingDigit = digit; break ; } } return missingDigit; } // Driver Code console.log(findMissingDigitCube( "219_" )); // Output: 7 console.log(findMissingDigitCube( "15_25" )); // Output: 6 |
7 6
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us