Рубрики

Минимальные цифры для удаления, чтобы сделать номер Perfect Square

Учитывая целое число n, нам нужно найти, сколько цифр удалить из числа, чтобы сделать его идеальным квадратом.

Примеры :

Input : 8314
Output: 81 2
Explanation: If we remove 3 and 4 number becomes 81 which is a perfect square.

Input : 57
Output : -1

Идея состоит в том, чтобы сгенерировать все возможные подпоследовательности и вернуть оптимальную строку, используя заданные биты . Предположим, у нас есть строка 8314. И используя биты, мы формируем все возможные подпоследовательности, т. Е.

8, 3, 83, 1, 81, 31, 831, 4, 84, 34, 834, 14, 814, 314, 8314.

После формирования всех возможных подпоследовательностей мы проверяем, какой из них является идеальным квадратом. И мы возвращаем идеальное квадратное число, которое имеет минимальную длину.

В приведенном выше примере три идеальных квадрата — это 1 4 и 81, поэтому ответом будет 81, потому что 81 имеет максимальную длину 2.

C ++

// C ++ программа для поиска необходимых минимальных цифр
// нужно удалить, чтобы сделать число идеальным
#include <bits/stdc++.h>

using namespace std;

  
// функция для проверки минимального количества цифр
// должен быть удален, чтобы сделать это число
// идеальный квадрат

int perfectSquare(string s)

{

    // размер строки

    int n = s.size();

  

    // наш окончательный ответ

    int ans = -1;

  

    // хранить строку, которая является идеальным квадратом.

    string num;

  

    // Мы делаем все возможные подпоследовательности

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

        string str = "";

          

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

              

            // проверить, установлен ли j-й бит или нет.

            if ((i >> j) & 1) {

                str += s[j];

            }

        }

  

        // мы не считаем число с ведущими нулями

        if (str[0] != '0') {

              

            // преобразовать нашу временную строку в целое число

            int temp = 0;

            for (int j = 0; j < str.size(); j++)

                temp = temp * 10 + (int)(str[j] - '0');

  

            int k = sqrt(temp);

  

            // проверка temp является идеальным квадратом или нет.

            if (k * k == temp) {

                  

                // берём строку максимального размера

                if (ans < (int)str.size()) {

                    ans = (int)str.size();

                    num = str;

                }

            }

        }

    }

  

    if (ans == -1)

        return ans;

    else {

          

        // распечатать PerfectSquare

        cout << num << " ";

        return n - ans;

    }

}

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

int main()

{

    cout << perfectSquare("8314") << endl;

    cout << perfectSquare("753") << endl;  

    return 0;

}

Джава

// Java-программа для поиска необходимых минимальных цифр
// нужно удалить, чтобы сделать число идеальным

import java.io.*;

import java.lang.*;

  

public class GFG {

      

    // функция для проверки минимума

    // количество цифр должно

    // быть удаленным, чтобы сделать это

    // нумерация идеального квадрата

    static int perfectSquare(String s)

    {

        // размер строки

        int n = s.length();

      

        // наш окончательный ответ

        int ans = -1;

      

        // хранить строку, которая

        // идеальный квадрат

        String num = "";

      

        // Мы делаем все возможные подпоследовательности

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

            String str = "";

              

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

                  

                // проверить, установлен ли j-й бит или нет.

                if (((i >> j) & 1) == 1) {

                    str += s.charAt(j);

                }

            }

      

            // мы не считаем число

            // с ведущими нулями

            if (str.charAt(0) != '0') {

                  

                // конвертируем наш временный

                // строка в целое число

                int temp = 0;

                for (int j = 0; j < 

                              str.length(); j++)

                    temp = temp * 10

                      (int)(str.charAt(j) - '0');

      

                int k = (int)Math.sqrt(temp);

      

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

                // квадрат или нет.

                if (k * k == temp) {

                      

                    // берём строку максимального размера

                    if (ans < (int)str.length()) {

                        ans = (int)str.length();

                        num = str;

                    }

                }

            }

        }

      

        if (ans == -1)

            return ans;

        else {

              

            // распечатать PerfectSquare

            System.out.print(num + " ");

            return n - ans;

        }

    }

      

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

    public static void main(String args[])

    {

        System.out.println(perfectSquare("8314"));

        System.out.println(perfectSquare("753"));

    }

}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

python3

# C ++ программа для поиска необходимого минимума
# цифры нужно убрать чтобы сделать
# номер идеальный квадрат

  

import math

# функция для проверки минимального количества
# цифры должны быть удалены, чтобы сделать
# это число идеальный квадрат

def perfectSquare(s) :

      

    # размер строки

    n = len(s)

  

    # наш окончательный ответ

    ans = -1

  

    # хранить строку, которая

    # идеальный квадрат.

    num = ""

  

    # Мы делаем все возможные подпоследовательности

    for i in range(1, (1 << n)) :

        str = ""

          

        for j in range(0, n) :

              

            # чтобы проверить j-й бит

            # установлено или нет.

            if ((i >> j) & 1) :

                str = str + s[j]

  

        # мы не считаем число

        # с ведущими нулями

        if (str[0] != '0') :

              

            # конвертировать наш временный

            # строка в целое число

            temp = 0;

            for j in range(0, len(str)) :

                temp = (temp * 10 + 

                 (ord(str[j]) - ord('0')))

  

            k = int(math.sqrt(temp))

  

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

            # квадрат или нет.

            if (k * k == temp) :

                  

                # брать максимальный размер

                # строка

                if (ans < len(str)) :

                    ans = len(str)

                    num = str

  

    if (ans == -1) :

        return ans

    else :         

          

        # print PerfectSquare

        print ("{} ".format(num), end="")

        return n - ans

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

print (perfectSquare("8314"))

print (perfectSquare("753"));

  
# Этот код предоставлен
# manishshaw1.

C #

// C # программа для поиска необходимых минимальных цифр
// нужно удалить, чтобы сделать число идеальным

using System;

class GFG {

      

    // функция для проверки минимума

    // количество цифр должно

    // быть удаленным, чтобы сделать это

    // нумерация идеального квадрата

    static int perfectSquare(string s)

    {

        // размер строки

        int n = s.Length;

      

        // наш окончательный ответ

        int ans = -1;

      

        // хранить строку, которая

        // идеальный квадрат

        string num = "";

      

        // Мы делаем все возможные подпоследовательности

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

            string str = "";

              

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

                  

                // проверить, установлен ли j-й бит или нет.

                if (((i >> j) & 1) == 1) {

                    str += s[j];

                }

            }

      

            // мы не считаем число

            // с ведущими нулями

            if (str[0] != '0') {

                  

                // конвертируем наш временный

                // строка в целое число

                int temp = 0;

                for (int j = 0; j < str.Length; j++)

                    temp = temp * 10 + (int)(str[j] - '0');

      

                int k = (int)Math.Sqrt(temp);

      

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

                // квадрат или нет.

                if (k * k == temp) {

                      

                    // берём строку максимального размера

                    if (ans < (int)str.Length) {

                        ans = (int)str.Length;

                        num = str;

                    }

                }

            }

        }

      

        if (ans == -1)

            return ans;

        else {

              

            // распечатать PerfectSquare

            Console.Write(num + " ");

            return n - ans;

        }

    }

      

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

    public static void Main()

    {

        Console.WriteLine(perfectSquare("8314"));

        Console.WriteLine(perfectSquare("753"));

    }

}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

PHP

<?php
// PHP программа для поиска нужного
// необходимо удалить минимальные цифры
// сделать число идеальным

  
// функция для проверки минимума
// количество цифр должно быть
// удалено, чтобы сделать это число
// идеальный квадрат

function perfectSquare($s)

{

    // размер строки

    $n = strlen($s);

  

    // наш окончательный ответ

    $ans = -1;

  

    // хранить строку, которая

    // идеальный квадрат

    $num = "";

  

    // Мы делаем все возможное

    // подпоследовательности

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

    {

        $str = "";

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

        {

              

            // проверить j-й бит

            // установлено или нет.

            if (($i >> $j) & 1) 

            {

                $str = $str.$s[$j];

            }

        }

  

        // мы не считаем

        // число с ведущими нулями

        if ($str[0] != '0'

        {

            // конвертируем наш временный

            // строка в целое число

            $temp = 0;

            for ($j = 0; $j < strlen($str); $j++)

                $temp = $temp * 10 + 

                        (ord($str[$j]) - ord('0'));

  

            $k = (int)(sqrt($temp));

  

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

            // квадрат или нет.

            if (($k * $k) == $temp)

            {

                  

                // берём строку максимального размера

                if ($ans < strlen($str)) 

                {

                    $ans = strlen($str);

                    $num = $str;

                }

            }

        }

    }

  

    if ($ans == -1) 

        return $ans;

    else 

    {         

        // распечатать PerfectSquare

        echo ($num." ");

        return ($n - $ans);

    }

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

echo (perfectSquare("8314"). "\n");

echo (perfectSquare("753"). "\n");

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)
?>

Выход :

81 2
-1

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

Минимальные цифры для удаления, чтобы сделать номер Perfect Square

0.00 (0%) 0 votes