資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究移除數字使其成為完全平方數的最小位數
問題陳述包括找到從數字中移除的最小數字數量，以使數字成為完全平方數。
完全平方數表示為 $\mathrm{x^{2}}$ 是一個正整數，它是整數與其自身的乘積。
我們將得到一個正數 N，我們需要找到我們可以從數字 N 中移除的最小數字數量，以使其成為完全平方數，即它是某個整數與其自身的乘積。
例如，N=42
我們可以從 N 中移除 1 位數字，即 2，使其成為完全平方數，這將是 4，這是一個完全平方數。
在這個問題中，我們將得到一個數字 N 作為輸入，我們的任務將是從 N 中移除最小數量的數字並列印完全平方數，以及從 N 中移除的數字數量以使其成為完全平方數。
在某些情況下，在從 N 中移除任意數量的數字後，它可能無法成為完全平方數，因此列印 −1。如果可以透過移除最小數量的數字形成多個完全平方數，則列印其中任何一個。
讓我們透過下面的示例瞭解問題。
輸入
N=490
輸出
49 1
說明− 輸入數字為 490，它不是完全平方數。如果我們從數字中移除一位數字，即 0，則數字變為 49，它是完全平方數 (7*7)。同時，如果我們從 N 中移除兩位數字，即 9 和 0，則數字變為 4，它也是完全平方數。
由於我們需要找到移除的最小數字數量以使 N 成為完全平方數，因此輸出將透過僅移除 1 位數字得到 49。
輸入
N=323
輸出
-1
說明− 給定的數字是 323，它不是完全平方數，並且從 N 中移除任意數量的數字，我們都無法使其成為完全平方數。因此，輸出為 −1。
讓我們瞭解查詢從 N 中移除的最小數字數量以使其成為完全平方數的演算法。
演算法
我們需要透過移除任意數量的數字來使給定的數字 N 成為完全平方數。我們需要找到要移除的最小數字數量以使其成為完全平方數。
為了找到從 N 中移除的最小數字數量以使其成為完全平方數，我們將簡單地找到數字 N 的所有子序列。例如，如果我們得到 N 為 8641，則該數字的所有子序列為
8, 6, 4, 1, 86, 84, 81, 64, 61, 41, 864, 861, 841, 641, 8641.
我們將檢查每個子序列是否為完全平方數，並找到可以透過從 N 中移除最小數字數量形成的完全平方數子序列。完全平方數為 4、81、64 和 841。要移除的最小數字數量從 N 中移除是 1，即 6，以使其成為完全平方數，即 841。
為了找到 N 的每個可能的子序列，我們將使用遞迴的概念來找到所有子序列。我們建立一個函式來查詢數字 N 的子序列，我們將在其中傳遞字串資料型別中的數字和一個空字串。
遞迴函式的邊界條件將是當字串數字的長度為 0 時，我們將返回該函式。否則，我們將字串的第一個字元儲存在一個變數中，並更新不包括第一個字元的字串。然後，我們將呼叫傳遞更新後的字串並向 ans 字串中新增字元的相同函式，然後在不向 ans 字串中新增的情況下呼叫，這最終將生成數字的所有可能的子序列。
一旦數字的字串長度為 0，即我們找到 N 的一個可能的子序列，如果 ans 字串不為空，我們將呼叫一個函式來檢查它是否為完全平方數，方法是從 N 中移除最小數字。
我們將初始化兩個變數來儲存要移除的最小數字數量以使 N 成為完全平方數，以及函式外部的 N，該函式是完全平方數，以獲得我們所需的輸出。
為了找到可以透過移除 N 的最小數字數量形成的完全平方數，我們將子序列的平方根儲存在 int 資料型別的變數中。如果變數的平方等於數字，那麼我們將檢查子序列的長度是否大於 a，然後我們將子序列的長度儲存在 a 中，並將子序列儲存在另一個變數中。
透過這種方式，我們可以獲得 N 的所有子序列，並找到最大長度的子序列，其與 N 大小的差將給出要移除的最小數字數量以使 N 成為完全平方數。
方法
為了實現我們的方法中查詢要移除的最小數字數量以使 N 成為完全平方數的演算法，需要遵循以下步驟
為了計算 N 的所有可能的子序列，我們呼叫一個遞迴函式，對於每個子序列，我們將檢查它是否是 N 的最長子序列，該子序列在我們的 C++ 方法中是完全平方數，以獲得要移除的最小數字和數字。
我們將初始化兩個變數來儲存是完全平方數的數字和要移除的最小數字數量。
我們將使用 to_string() 函式將輸入數字 N 轉換為字串，並呼叫遞迴函式，該函式將為我們提供最長可能長度的完全平方數。
列印完全平方數和移除的最小數字。
示例
//C++ code to find the minimum number of digits to be removed to make N a perfect square
#include<bits/stdc++.h>
using namespace std;
int res=-1; //to store perfect square after removing digits from N
int a=0; //to store the number of digits in perfect square
//to check if the subsequence is a perfect square of maximum length possible
void checkMaximum(int m,string ans)
{
int check=sqrt(m); //finding square root of subsequence
if(check*check==m)
{
if(a < ans.size()) //if length of subsequence is greater than a
{
a = ans.size(); //store length of subsequence in a
res = m; //store number in res which is a perfect square
}
}
}
//to find all the possible subsequences
void subsequence(string str,string ans){
if(str.length() == 0){
if( !ans.empty()){
int temp = stoi(ans); //converting subsequence in int
checkMaximum(temp, ans); //checking if it is the perfect square by removing minimum digits
}
return;
}
//generating all the possible subsequences using recursion
char ch = str[0];
string roq = str.substr(1);
subsequence(roq, ans + ch);
subsequence(roq, ans);
}
int main()
{
int N=78467;
string str =to_string(N); //converting N into a string using inbuilt function
string ans =""; //string to store all the possible subsequences of N
//calling the function
subsequence(str, ans);
if(res==-1){
cout<<res<<endl;
}
else{
cout<<res<<endl;
//difference of str size and a which is the length of perfect square will give minimum number of digits
cout<<str.size()-a<<endl;
}
return 0;
}
輸出
784 2
時間複雜度− $\mathrm{O(2^{n})}$，其中 n 是遞迴樹的深度。
空間複雜度− $\mathrm{O(2^{n})}$，因為遞迴函式使用堆疊記憶體。
結論
本文討論了查詢要從 N 中移除的最小數字數量以使其成為完全平方數的問題。我們使用遞迴檢查 N 的所有子序列，以檢查每個子序列是否是我們 C++ 方法中最長可能長度的完全平方數，以獲得要移除的最小數字和數字。
我希望您在閱讀本文後已經瞭解了問題和解決問題的方法。
472 次檢視
