Given an integer n, we need to find how many digits remove from the number to make it a perfect square.
Examples :
Input : 8314
Output: 81 2
Explanation: If we remove 3 and 4 number becomes 81 which is a perfect square.Input : 57
Output : -1
The idea is to generate all possible subsequences and return the optimal string using set bits. Let’s suppose we have a string 8314. And using set bits we form all possible subsequences i.e.,
8, 3, 83, 1, 81, 31, 831, 4, 84, 34, 834, 14, 814, 314, 8314.
After forming all possible subsequences, we check which one is the perfect square. And we return a perfect square number that has the minimum length.
In the above example, three perfect squares are 1 4, and 81, so the answer would be 81 because 81 has the max length of 2.
C++
// C++ program to find required minimum digits// need to remove to make a number perfect square#include <bits/stdc++.h>using namespace std;// function to check minimum number of digits// should be removed to make this number// a perfect squareint perfectSquare(string s){ // size of the string int n = s.size(); // our final answer int ans = -1; // to store string which is perfect square. string num; // We make all possible subsequences for (int i = 1; i < (1 << n); i++) { string str = ""; for (int j = 0; j < n; j++) { // to check jth bit is set or not. if ((i >> j) & 1) { str += s[j]; } } // we do not consider a number with leading zeros if (str[0] != '0') { // convert our temporary string into integer int temp = 0; for (int j = 0; j < str.size(); j++) temp = temp * 10 + (int)(str[j] - '0'); int k = sqrt(temp); // checking temp is perfect square or not. if (k * k == temp) { // taking maximum sized string if (ans < (int)str.size()) { ans = (int)str.size(); num = str; } } } } if (ans == -1) return ans; else { // print PerfectSquare cout << num << " "; return n - ans; }}// Driver codeint main(){ cout << perfectSquare("8314") << endl; cout << perfectSquare("753") << endl; return 0;} |
Java
// Java program to find required minimum digits// need to remove to make a number perfect squareimport java.io.*;import java.lang.*;public class GFG { // function to check minimum // number of digits should // be removed to make this // number a perfect square static int perfectSquare(String s) { // size of the string int n = s.length(); // our final answer int ans = -1; // to store string which // is perfect square. String num = ""; // We make all possible subsequences for (int i = 1; i < (1 << n); i++) { String str = ""; for (int j = 0; j < n; j++) { // to check jth bit is set or not. if (((i >> j) & 1) == 1) { str += s.charAt(j); } } // we do not consider a number // with leading zeros if (str.charAt(0) != '0') { // convert our temporary // string into integer 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); // checking temp is perfect // square or not. if (k * k == temp) { // taking maximum sized string if (ans < (int)str.length()) { ans = (int)str.length(); num = str; } } } } if (ans == -1) return ans; else { // print PerfectSquare System.out.print(num + " "); return n - ans; } } // Driver code public static void main(String args[]) { System.out.println(perfectSquare("8314")); System.out.println(perfectSquare("753")); }}// This code is contributed by // Manish Shaw (manishshaw1) |
Python3
# C++ program to find required minimum # digits need to remove to make a # number perfect squareimport math# function to check minimum number of# digits should be removed to make# this number a perfect squaredef perfectSquare(s) : # size of the string n = len(s) # our final answer ans = -1 # to store string which is # perfect square. num = "" # We make all possible subsequences for i in range(1, (1 << n)) : str = "" for j in range(0, n) : # to check jth bit is # set or not. if ((i >> j) & 1) : str = str + s[j] # we do not consider a number # with leading zeros if (str[0] != '0') : # convert our temporary # string into integer temp = 0; for j in range(0, len(str)) : temp = (temp * 10 + (ord(str[j]) - ord('0'))) k = int(math.sqrt(temp)) # checking temp is perfect # square or not. if (k * k == temp) : # taking maximum sized # string if (ans < len(str)) : ans = len(str) num = str if (ans == -1) : return ans else : # print PerfectSquare print ("{} ".format(num), end="") return n - ans # Driver codeprint (perfectSquare("8314"))print (perfectSquare("753"));# This code is contributed by # manishshaw1. |
C#
// C# program to find required minimum digits// need to remove to make a number perfect squareusing System;class GFG { // function to check minimum // number of digits should // be removed to make this // number a perfect square static int perfectSquare(string s) { // size of the string int n = s.Length; // our final answer int ans = -1; // to store string which // is perfect square. string num = ""; // We make all possible subsequences for (int i = 1; i < (1 << n); i++) { string str = ""; for (int j = 0; j < n; j++) { // to check jth bit is set or not. if (((i >> j) & 1) == 1) { str += s[j]; } } // we do not consider a number // with leading zeros if (str[0] != '0') { // convert our temporary // string into integer int temp = 0; for (int j = 0; j < str.Length; j++) temp = temp * 10 + (int)(str[j] - '0'); int k = (int)Math.Sqrt(temp); // checking temp is perfect // square or not. if (k * k == temp) { // taking maximum sized string if (ans < (int)str.Length) { ans = (int)str.Length; num = str; } } } } if (ans == -1) return ans; else { // print PerfectSquare Console.Write(num + " "); return n - ans; } } // Driver code public static void Main() { Console.WriteLine(perfectSquare("8314")); Console.WriteLine(perfectSquare("753")); }}// This code is contributed by // Manish Shaw (manishshaw1) |
PHP
<?php// PHP program to find required // minimum digits need to remove // to make a number perfect square// function to check minimum // number of digits should be// removed to make this number// a perfect squarefunction perfectSquare($s){ // size of the string $n = strlen($s); // our final answer $ans = -1; // to store string which // is perfect square. $num = ""; // We make all possible // subsequences for ($i = 1; $i < (1 << $n); $i++) { $str = ""; for ($j = 0; $j < $n; $j++) { // to check jth bit // is set or not. if (($i >> $j) & 1) { $str = $str.$s[$j]; } } // we do not consider a // number with leading zeros if ($str[0] != '0') { // convert our temporary // string into integer $temp = 0; for ($j = 0; $j < strlen($str); $j++) $temp = $temp * 10 + (ord($str[$j]) - ord('0')); $k = (int)(sqrt($temp)); // checking temp is perfect // square or not. if (($k * $k) == $temp) { // taking maximum sized string if ($ans < strlen($str)) { $ans = strlen($str); $num = $str; } } } } if ($ans == -1) return $ans; else { // print PerfectSquare echo ($num." "); return ($n - $ans); }} // Driver codeecho (perfectSquare("8314"). "\n");echo (perfectSquare("753"). "\n");// This code is contributed by // Manish Shaw (manishshaw1)?> |
Javascript
<script>// Javascript program to find required// minimum digits need to remove// to make a number perfect square// Function to check minimum// number of digits should be// removed to make this number// a perfect squarefunction perfectSquare(s) { // Size of the string let n = s.length; // Our final answer let ans = -1; // To store string which // is perfect square. let num = ""; // We make all possible // subsequences for(let i = 1; i < (1 << n); i++) { let str = ""; for(j = 0; j < n; j++) { // To check jth bit // is set or not. if ((i >> j) & 1) { str = str + s[j]; } } // We do not consider a // number with leading zeros if (str[0] != '0') { // Convert our temporary // string into integer let temp = 0; for(let j = 0; j < str.length; j++) temp = temp * 10 + (str[j].charCodeAt(0) - '0'.charCodeAt(0)); k = Math.floor(Math.sqrt(temp)); // Checking temp is perfect // square or not. if ((k * k) == temp) { // Taking maximum sized string if (ans < str.length) { ans = str.length; num = str; } } } } if (ans == -1) return ans; else { // Print PerfectSquare document.write(num + " "); return (n - ans); }}// Driver codedocument.write(perfectSquare("8314") + "<br>");document.write(perfectSquare("753") + "<br>");// This code is contributed by gfgking</script> |
Output
81 2 -1
Time Complexity: O(n * 2n)
Auxiliary Space: O(2n)
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!
