Рубрики

Найти самый большой куб, образованный удалением минимальных цифр из числа

Учитывая число n, задача состоит в том, чтобы найти самый большой совершенный куб, который можно сформировать, удалив минимальные цифры (возможно, 0) из числа.
X называется идеальным кубом, если X = Y 3 для некоторого Y.

Примеры:

Input : 4125
Output : 125
Explanation
125 = 53. We can form 125 by deleting digit 4 from 4125

Input : 876
Output :8
Explanation
8 = 23. We can form 8 by deleting digits 7 and 6 from 876

Мы можем генерировать кубы всех чисел до от 1 до N 1/3 (0 не рассматривается, поскольку 0 не считается идеальным кубом). Мы перебираем кубы от самых больших до самых маленьких.
Теперь, если мы посмотрим на число n, данное нам, то мы знаем, что это число содержит только log (n) + 1 цифра, таким образом, мы можем эффективно подойти к проблеме, если будем рассматривать это число n как строку в дальнейшем.
Выполняя итерацию по совершенным кубам, мы проверяем, является ли совершенный куб подпоследовательностью числа n, если он представлен в виде строки. Если это так, то удаления, необходимые для изменения числа n на текущий совершенный куб, будут:

No of deleted digits = No of digits in number n - 
                       Number of digits in current 
                                      perfect cube

Поскольку нам нужно наибольшее число кубов, мы пересекаем массив предварительно обработанных кубов в обратном порядке.

C ++

/ * C ++ код для реализации максимально совершенного куба

   формируется после удаления минимальных цифр * /

#include <bits/stdc++.h>

using namespace std;

  
// Возвращает вектор предварительно обработанных совершенных кубов

vector<string> preProcess(long long int n)

{

    vector<string> preProcessedCubes;

    for (int i = 1; i * i * i <= n; i++) {

        long long int iThCube = i * i * i;

  

        // преобразовать куб в строку и вставить в

        // preProcessedCubes vector

        string cubeString = to_string(iThCube);

        preProcessedCubes.push_back(cubeString);

    }

    return preProcessedCubes;

}

  
/ * Сервисная функция для findLargestCube ().

   Возвращает наибольший номер куба, который может быть сформирован * /

string findLargestCubeUtil(string num, 

                    vector<string> preProcessedCubes)

{

    // перевернуть предварительно обработанные кубы, чтобы мы

    // в начале самый большой куб

    // вектора

    reverse(preProcessedCubes.begin(), preProcessedCubes.end());

  

    int totalCubes = preProcessedCubes.size();

  

    // перебрать все кубы

    for (int i = 0; i < totalCubes; i++) {

        string currCube = preProcessedCubes[i];

  

        int digitsInCube = currCube.length();

        int index = 0;

        int digitsInNumber = num.length();

        for (int j = 0; j < digitsInNumber; j++) {

  

            // проверяем текущую цифру куба

            // совпадает с номером num

            if (num[j] == currCube[index]) 

                index++;

              

            if (digitsInCube == index)                 

                return currCube;            

        }

    }

  

    // если управление достигает здесь, его

    // невозможно сформировать идеальный куб

    return "Not Possible";

}

  
// обертка для findLargestCubeUtil ()

void findLargestCube(long long int n)

{

    // предварительно обработать идеальные кубы

    vector<string> preProcessedCubes = preProcess(n);

  

    // преобразовать число n в строку

    string num = to_string(n);

  

    string ans = findLargestCubeUtil(num, preProcessedCubes);

  

    cout << "Largest Cube that can be formed from "

         << n << " is " << ans << endl;

}

  
// Код драйвера

int main()

{

    long long int n;

    n = 4125;

    findLargestCube(n);

  

    n = 876;

    findLargestCube(n);

  

    return 0;

}

Джава

/ * Java-код для реализации максимально совершенного куба
формируется после удаления минимальных цифр * /

import java.util.*;

class GFG 

{

  

    // Возвращает вектор предварительно обработанных совершенных кубов

    static Vector<String> preProcess(int n) 

    {

        Vector<String> preProcessedCubes = new Vector<>();

        for (int i = 1; i * i * i <= n; i++)

        {

            int iThCube = i * i * i;

  

            // преобразовать куб в строку и вставить в

            // preProcessedCubes vector

            String cubeString = String.valueOf(iThCube);

            preProcessedCubes.add(cubeString);

        }

        return preProcessedCubes;

    }

  

    / * Сервисная функция для findLargestCube ().

    Возвращает наибольший номер куба, который может быть сформирован * /

    static String findLargestCubeUtil(String num,

            Vector<String> preProcessedCubes) 

    {

        // перевернуть предварительно обработанные кубы, чтобы мы

        // в начале самый большой куб

        // вектора

        Collections.reverse(preProcessedCubes);

  

        int totalCubes = preProcessedCubes.size();

  

        // перебрать все кубы

        for (int i = 0; i < totalCubes; i++)

        {

            String currCube = preProcessedCubes.get(i);

  

            int digitsInCube = currCube.length();

            int index = 0;

            int digitsInNumber = num.length();

            for (int j = 0; j < digitsInNumber; j++)

            {

  

                // проверяем текущую цифру куба

                // совпадает с номером num

                if (num.charAt(j) == currCube.charAt(index)) 

                {

                    index++;

                }

  

                if (digitsInCube == index) 

                {

                    return currCube;

                }

            }

        }

  

        // если управление достигает здесь, его

        // невозможно сформировать идеальный куб

        return "Not Possible";

    }

  

    // обертка для findLargestCubeUtil ()

    static void findLargestCube(int n) 

    {

        // предварительно обработать идеальные кубы

        Vector<String> preProcessedCubes = preProcess(n);

  

        // преобразовать число n в строку

        String num = String.valueOf(n);

  

        String ans = findLargestCubeUtil(num, preProcessedCubes);

  

        System.out.println("Largest Cube that can be formed from "

                + n + " is " + ans);

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int n;

        n = 4125;

        findLargestCube(n);

  

        n = 876;

        findLargestCube(n);

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 код для максимальной реализации
# куб, сформированный после удаления минимальных цифр

import math as mt

  
# Возвращает вектор предварительно обработанного
# идеальные кубики

def preProcess(n):

  

    preProcessedCubes = list()

    for i in range(1, mt.ceil(n**(1. / 3.))):

        iThCube = i**3

          

        # преобразовать куб в строку и

        # вставить в вектор preProcessedCubes

        cubeString = str(iThCube)

        preProcessedCubes.append(cubeString)

          

    return preProcessedCubes

  
# Сервисная функция для findLargestCube ().
# Возвращает самый большой номер куба, который
# может быть сформирован

def findLargestCubeUtil(num,preProcessedCubes):

      

    # перевернуть предварительно обработанные кубы так

    # что у нас самый большой куб в

    # начало вектора

    preProcessedCubes = preProcessedCubes[::-1]

  

    totalCubes = len(preProcessedCubes)

  

    # перебрать все кубы

    for i in range(totalCubes):

        currCube = preProcessedCubes[i]

  

        digitsInCube = len(currCube)

        index = 0

        digitsInNumber = len(num)

        for j in range(digitsInNumber):

              

            # проверить, если текущая цифра куба

            # соответствует номеру номера

            if (num[j] == currCube[index]): 

                index += 1

              

            if (digitsInCube == index):             

                return currCube         

      

    # если управление достигает здесь, его

    # невозможно сформировать идеальный куб

    return "Not Possible"

  
# обертка для findLargestCubeUtil ()

def findLargestCube(n):

  

    # предварительная обработка идеальных кубиков

    preProcessedCubes = preProcess(n)

  

    num = str(n)

  

    ans = findLargestCubeUtil(num, preProcessedCubes)

  

    print("Largest Cube that can be formed from"

                                    n, "is", ans)

  
Код водителя

n = 4125

findLargestCube(n)

  

n = 876

findLargestCube(n)

      
# Этот код добавлен
# от mohit kumar 29

C #

/ * C # код для реализации максимально совершенного куба
формируется после удаления минимальных цифр * /

using System;

using System.Collections.Generic;

  

class GFG 

  

    // Возвращает вектор предварительно обработанных совершенных кубов

    static List<String> preProcess(int n) 

    

        List<String> preProcessedCubes = new List<String>(); 

        for (int i = 1; i * i * i <= n; i++) 

        

            int iThCube = i * i * i; 

  

            // преобразовать куб в строку и вставить в

            // preProcessedCubes vector

            String cubeString = String.Join("",iThCube); 

            preProcessedCubes.Add(cubeString); 

        

        return preProcessedCubes; 

    

  

    / * Сервисная функция для findLargestCube ().

    Возвращает наибольший номер куба, который может быть сформирован * /

    static String findLargestCubeUtil(String num, 

            List<String> preProcessedCubes) 

    

        // перевернуть предварительно обработанные кубы, чтобы мы

        // в начале самый большой куб

        // вектора

        preProcessedCubes.Reverse(); 

  

        int totalCubes = preProcessedCubes.Count; 

  

        // перебрать все кубы

        for (int i = 0; i < totalCubes; i++) 

        

            String currCube = preProcessedCubes[i]; 

  

            int digitsInCube = currCube.Length; 

            int index = 0; 

            int digitsInNumber = num.Length; 

            for (int j = 0; j < digitsInNumber; j++) 

            

  

                // проверяем текущую цифру куба

                // совпадает с номером num

                if (num[j] == currCube[index]) 

                

                    index++; 

                

  

                if (digitsInCube == index) 

                

                    return currCube; 

                

            

        

  

        // если управление достигает здесь, его

        // невозможно сформировать идеальный куб

        return "Not Possible"

    

  

    // обертка для findLargestCubeUtil ()

    static void findLargestCube(int n) 

    

        // предварительно обработать идеальные кубы

        List<String> preProcessedCubes = preProcess(n); 

  

        // преобразовать число n в строку

        String num = String.Join("",n); 

  

        String ans = findLargestCubeUtil(num, preProcessedCubes); 

  

        Console.WriteLine("Largest Cube that can be formed from "

                + n + " is " + ans); 

    

  

    // Код драйвера

    public static void Main(String[] args) 

    

        int n; 

        n = 4125; 

        findLargestCube(n); 

  

        n = 876; 

        findLargestCube(n); 

    

  
// Этот код предоставлен Rajput-Ji

PHP

<?php
// PHP-код для реализации максимально совершенного
// куб, сформированный после удаления минимальных цифр

  
// Возвращает вектор предварительно обработанного
// идеальные кубики

function preProcess($n)

{

  

    $preProcessedCubes = array();

    for ($i = 1; $i * $i * $i < $n; $i++)

    {

        $iThCube = $i * $i * $i;

          

        // преобразовать куб в строку и

        // вставляем в вектор preProcessedCubes

        $cubeString = strval($iThCube);

        array_push($preProcessedCubes,$cubeString);

    }

    return $preProcessedCubes;

}

  
// Сервисная функция для findLargestCube ().
// Возвращает самый большой номер куба, который
// можно сформировать

function findLargestCubeUtil($num,$preProcessedCubes)

    // перевернуть предварительно обработанные кубы так

    // что у нас самый большой куб в

    // начало вектора

    $preProcessedCubes = array_reverse($preProcessedCubes);

  

    $totalCubes = count($preProcessedCubes);

  

    // перебрать все кубы

    for($i = 0; $i < $totalCubes; $i++)

    {

        $currCube = $preProcessedCubes[$i];

  

        $digitsInCube = strlen($currCube);

        $index = 0;

        $digitsInNumber = strlen($num);

        for ($j = 0; $j < $digitsInNumber; $j++)

        {

              

            // проверяем текущую цифру куба

            // совпадает с номером num

            if ($num[$j] == $currCube[$index]) 

                $index += 1;

              

            if ($digitsInCube == $index)             

                return $currCube;     

        }

    }

    // если управление достигает здесь, его

    // невозможно сформировать идеальный куб

    return "Not Possible";

}

  
// обертка для findLargestCubeUtil ()

function findLargestCube($n)

{

  

    // предварительно обработать идеальные кубы

    $preProcessedCubes = preProcess($n);

  

    $num = strval($n);

  

    $ans = findLargestCubeUtil($num, $preProcessedCubes);

  

    print("Largest Cube that can be formed from ".$n." is ".$ans."\n");

}

  
// Код драйвера

$n = 4125;

findLargestCube($n);

  

$n = 876;

findLargestCube($n)

      
// Этот код предоставлен mits
?>

Выход:

Largest Cube that can be formed from 4125 is 125
Largest Cube that can be formed from 876 is 8

Сложность по времени вышеприведенного алгоритма составляет O (N 1/3 log (N) log (N)) из-за того, что количество цифр в N равно Log (N) + 1.

Рекомендуемые посты:

Найти самый большой куб, образованный удалением минимальных цифр из числа

0.00 (0%) 0 votes