Given an integer N, find the smallest N digit number such that the sum of the square of digits (in decimal representation) of the number is also a perfect square. If no such number exists, print -1.
Examples:
Input : N = 2
Output : 34
Explanation:
The smallest possible 2 digit number whose sum of square of digits is a perfect square is 34 because 32 + 42 = 52.
Input : N = 1
Output : 1
Explanation:
The smallest possible 1 digit number is 1 itself.
Method 1:
To solve the problem mentioned above we can use Backtracking. Since we want to find the minimum N digit number satisfying the given condition, the answer will have digits in non-decreasing order. Therefore we generate the possible numbers recursively keeping track of following in each recursive step :
- position: the current position of the recursive step i.e. which position digit is being placed.
- prev: the previous digit placed because the current digit has to be greater than equal to prev.
- sum: the sum of squares of digits placed till now. When digits are placed, this will be used to check whether the sum of squares of all digits placed is a perfect square or not.
- A vector which stores what all digits have been placed till this position.
If placing a digit at a position and moving to the next recursive step leads to a possible solution then return 1, else backtrack.
Below is the implementation of the above approach:
C++
// C++ implementation to find Smallest N// digit number whose sum of square// of digits is a Perfect Square#include <bits/stdc++.h>using namespace std;// function to check if// number is a perfect squareint isSquare(int n){ int k = sqrt(n); return (k * k == n);}// function to calculate the// smallest N digit numberint calculate(int pos, int prev, int sum, vector<int>& v){ if (pos == v.size()) return isSquare(sum); // place digits greater than equal to prev for (int i = prev; i <= 9; i++) { v[pos] = i; sum += i * i; // check if placing this digit leads // to a solution then return it if (calculate(pos + 1, i, sum, v)) return 1; // else backtrack sum -= i * i; } return 0;}string minValue(int n){ vector<int> v(n); if (calculate(0, 1, 0, v)) { // create a string representing // the N digit number string answer = ""; for (int i = 0; i < v.size(); i++) answer += char(v[i] + '0'); return answer; } else return "-1";}// driver codeint main(){ // initialise N int N = 2; cout << minValue(N); return 0;} |
Java
// Java implementation to find Smallest N// digit number whose sum of square// of digits is a Perfect Squareimport java.io.*;import java.util.*;class GFG{ // function to check if// number is a perfect squarestatic int isSquare(int n){ int k = (int)Math.sqrt(n); return k * k == n ? 1 : 0;}// Function to calculate the// smallest N digit numberstatic int calculate(int pos, int prev, int sum, int[] v){ if (pos == v.length) return isSquare(sum); // Place digits greater than equal to prev for(int i = prev; i <= 9; i++) { v[pos] = i; sum += i * i; // Check if placing this digit leads // to a solution then return it if (calculate(pos + 1, i, sum, v) != 0) return 1; // Else backtrack sum -= i * i; } return 0;}static String minValue(int n){ int[] v = new int[n]; if (calculate(0, 1, 0, v) != 0) { // Create a string representing // the N digit number String answer = ""; for(int i = 0; i < v.length; i++) answer += (char)(v[i] + '0'); return answer; } else return "-1";}// Driver codepublic static void main(String[] args){ // Initialise N int N = 2; System.out.println(minValue(N));}}// This code is contributed by jrishabh99 |
Python3
# Python3 implementation to find Smallest N# digit number whose sum of square# of digits is a Perfect Squarefrom math import sqrt# function to check if# number is a perfect squaredef isSquare(n): k = int(sqrt(n)) return (k * k == n)# function to calculate the# smallest N digit numberdef calculate(pos, prev, sum, v): if (pos == len(v)): return isSquare(sum) # place digits greater than equal to prev for i in range(prev, 9 + 1): v[pos] = i sum += i * i # check if placing this digit leads # to a solution then return it if (calculate(pos + 1, i, sum, v)): return 1 # else backtrack sum -= i * i return 0def minValue(n): v = [0]*(n) if (calculate(0, 1, 0, v)): # create a representing # the N digit number answer = "" for i in range(len(v)): answer += chr(v[i] + ord('0')) return answer else: return "-1"# Driver codeif __name__ == '__main__': # initialise N N = 2 print(minValue(N))# This code is contributed by mohit kumar 29 |
C#
// C# implementation to find Smallest N// digit number whose sum of square// of digits is a Perfect Squareusing System;class GFG{ // function to check if// number is a perfect squarestatic int isSquare(int n){ int k = (int)Math.Sqrt(n); return k * k == n ? 1 : 0;}// Function to calculate the// smallest N digit numberstatic int calculate(int pos, int prev, int sum, int[] v){ if (pos == v.Length) return isSquare(sum); // Place digits greater than equal to prev for(int i = prev; i <= 9; i++) { v[pos] = i; sum += i * i; // Check if placing this digit leads // to a solution then return it if (calculate(pos + 1, i, sum, v) != 0) return 1; // Else backtrack sum -= i * i; } return 0;}static string minValue(int n){ int[] v = new int[n]; if (calculate(0, 1, 0, v) != 0) { // Create a string representing // the N digit number string answer = ""; for(int i = 0; i < v.Length; i++) answer += (char)(v[i] + '0'); return answer; } else return "-1";}// Driver codepublic static void Main(){ // Initialise N int N = 2; Console.Write(minValue(N));}} |
Javascript
<script>// Javascript implementation to find Smallest N// digit number whose sum of square// of digits is a Perfect Square// function to check if// number is a perfect squarefunction isSquare(n){ let k = Math.floor(Math.sqrt(n)); return k * k == n ? 1 : 0;} // Function to calculate the// smallest N digit numberfunction calculate(pos, prev, sum, v){ if (pos == v.length) return isSquare(sum); // Place digits greater than equal to prev for(let i = prev; i <= 9; i++) { v[pos] = i; sum += i * i; // Check if placing this digit leads // to a solution then return it if (calculate(pos + 1, i, sum, v) != 0) return 1; // Else backtrack sum -= (i * i); } return 0;} function minValue(n){ let v = Array.from({length: n}, (_, i) => 0); if (calculate(0, 1, 0, v) != 0) { // Create a string representing // the N digit number let answer = ""; for(let i = 0; i < v.length; i++) answer += (v[i] + 0); return answer; } else return "-1";} // Driver Code // Initialise N let N = 2; document.write(minValue(N)); // This code is contributed by sanjoy_62.</script> |
Output
34
Time Complexity: O(sqrt(n))
Auxiliary Space: O(n)
Method 2:
The above-mentioned problem can also be solved using Dynamic Programming. If we observe the question carefully we see that it can be converted to the standard Coin Change problem. Given N as the number of digits, the base answer will be N 1’s, the sum of the square of whose digits will be N.
- If N itself is a perfect square then the N times 1 will be the final answer.
- Otherwise, we will have to replace some 1’s in the answer with other digits from 2-9. Each replacement in the digit will increase the sum of the square by a certain amount and since 1 can be changed to only 8 other possible digits there are only 8 such possible increments. For example, if 1 is changed to 2, then increment will be 22 – 12 = 3. Similarly, all possible changes are : {3, 8, 15, 24, 35, 48, 63, 80}.
So the problem now can be interpreted as having 8 kinds of coins of the aforementioned values and we can use any coin any number of times to create the required sum. The sum of squares will lie in the range of N (all digits are 1) to 81 * N (all digits are 9). We just have to consider perfect square sums in the range and use the idea of coin change to find the N digits that will be in the answer. One important point we need to take into account is that we have to find the smallest N digit number not the number with the smallest square sum of digits.
Below is the implementation of the above-mentioned approach:
C++
// C++ implementation to find the Smallest// N digit number whose sum of square// of digits is a Perfect Square#include <bits/stdc++.h>using namespace std;long long value[8100006];int first[8100006];// array for all possible changesint coins[8] = { 3, 8, 15, 24, 35, 48, 63, 80 };void coinChange(){ const long long inf = INT_MAX; // iterating till 81 * N // since N is at max 10^5 for (int x = 1; x <= 8100005; x++) { value[x] = inf; for (auto c : coins) { if (x - c >= 0 && value[x - c] + 1 < value[x]) { value[x] = min(value[x], value[x - c] + 1); // least value of coin first[x] = c; } } }}// function to find the// minimum possible valuestring minValue(int n){ // applying coin change for all the numbers coinChange(); string answer = ""; // check if number is // perfect square or not if ((sqrt(n) * sqrt(n)) == n) { for (int i = 0; i < n; i++) answer += "1"; return answer; } long long hi = 81 * n; long long lo = sqrt(n); // keeps a check whether // number is found or not bool found = false; long long upper = 81 * n; long long lower = n; // sorting suffix strings string suffix; bool suf_init = false; while ((lo * lo) <= hi) { lo++; long long curr = lo * lo; long long change = curr - n; if (value[change] <= lower) { // build a suffix string found = true; if (lower > value[change]) { // number to be used for updation of lower, // first values that will be used // to construct the final number later lower = value[change]; upper = change; suffix = ""; suf_init = true; int len = change; while (len > 0) { int k = sqrt(first[len] + 1); suffix = suffix + char(k + 48); len = len - first[len]; } } else if (lower == value[change]) { string tempsuf = ""; int len = change; while (len > 0) { int k = sqrt(first[len] + 1); tempsuf = tempsuf + char(k + 48); len = len - first[len]; } if (tempsuf < suffix or suf_init == false) { lower = value[change]; upper = change; suffix = tempsuf; suf_init = true; } } } } // check if number is found if (found) { // construct the number from first values long long x = lower; for (int i = 0; i < (n - x); i++) answer += "1"; long long temp = upper; // fill in rest of the digits while (temp > 0) { int dig = sqrt(first[temp] + 1); temp = temp - first[temp]; answer += char(dig + '0'); } return answer; } else return "-1";}// driver codeint main(){ // initialise N int N = 2; cout << minValue(N); return 0;} |
Java
// Java implementation to find the Smallest// N digit number whose sum of square// of digits is a Perfect Squareimport java.io.*;import java.util.*;class GFG { static long[] value = new long[(int)8100006]; static int[] first = new int[8100006]; // array for all possible changes static int coins[] = { 3, 8, 15, 24, 35, 48, 63, 80 }; public static void coinChange() { final long inf = Integer.MAX_VALUE; // iterating till 81 * N // since N is at max 10^5 for (int x = 1; x <= 8100005; x++) { value[x] = inf; for (int c : coins) { if (x - c >= 0 && value[x - c] + 1 < value[x]) { value[x] = Math.min(value[x], value[x - c] + 1); // least value of coin first[x] = c; } } } } // function to find the // minimum possible value public static String minValue(int n) { // applying coin change for all the numbers coinChange(); String answer = ""; // check if number is // perfect square or not if ((Math.sqrt(n) * Math.sqrt(n)) == n) { for (int i = 0; i < n; i++) answer += "1"; return answer; } long hi = 81 * n; long lo = (long)Math.sqrt(n); // keeps a check whether // number is found or not boolean found = false; long upper = 81 * n; long lower = n; // sorting suffix strings String suffix = ""; boolean suf_init = false; while ((lo * lo) <= hi) { lo++; long curr = lo * lo; long change = curr - n; if (value[(int)change] <= lower) { // build a suffix string found = true; if (lower > value[(int)change]) { // number to be used for updation of // lower, first values that will be used // to construct the final number later lower = value[(int)change]; upper = change; suffix = ""; suf_init = true; int len = (int)change; while (len > 0) { int k = (int)Math.sqrt(first[len] + 1); suffix = suffix + (char)(k + 48); len = len - first[len]; } } else if (lower == value[(int)change]) { String tempsuf = ""; int len = (int)change; while (len > 0) { int k = (int)Math.sqrt(first[len] + 1); tempsuf = tempsuf + (char)(k + 48); len = len - first[len]; } if ((tempsuf.compareTo(suffix) < 0) || (suf_init == false)) { lower = value[(int)change]; upper = change; suffix = tempsuf; suf_init = true; } } } } // check if number is found if (found) { // construct the number from first values long x = lower; for (int i = 0; i < (n - x); i++) answer += "1"; long temp = upper; // fill in rest of the digits while (temp > 0) { int dig = (int)Math.sqrt(first[(int)temp] + 1); temp = temp - first[(int)temp]; answer += (char)(dig + '0'); } return answer; } else return "-1"; } // Driver code public static void main(String[] args) { // initialise N int N = 2; System.out.println(minValue(N)); }}// This code is contributed by Palak Gupta |
Python3
# Python3 implementation to find the Smallest# N digit number whose sum of square# of digits is a Perfect Squarevalue = [0 for _ in range(810006)];first = [0 for _ in range(810006)];# array for all possible changescoins = [ 3, 8, 15, 24, 35, 48, 63, 80 ];def coinChange(): inf = 99999999; # iterating till 81 * N # since N is at max 10^5 for x in range(1, 810005 + 1): value[x] = inf; for c in coins: if (x - c >= 0 and value[x - c] + 1 < value[x]) : value[x] = min(value[x], value[x - c] + 1); # least value of coin first[x] = c; # function to find the# minimum possible valuedef minValue( n): # applying coin change for all the numbers coinChange(); answer = ""; # check if number is # perfect square or not if (n == (int(n ** 0.5)) ** 0.5): for i in range(n): answer += "1" return answer; hi = 81 * n; lo = int((n ** 0.5)); # keeps a check whether # number is found or not found = False; upper = 81 * n; lower = n; # sorting suffix lets suffix = ""; suf_init = False; while ((lo * lo) <= hi) : lo += 1 curr = lo * lo; change = curr - n; if (value[change] <= lower) : # build a suffix let found = True; if (lower > value[change]) : # number to be used for updation of lower, # first values that will be used # to construct the final number later lower = value[change]; upper = change; suffix = ""; suf_init = true; len1 = change; while (len1 > 0) : k = int((first[len1] + 1) ** 0.5); suffix = suffix + str(k) len1 = len1 - first[len1]; elif (lower == value[change]) : tempsuf = ""; len1 = change; while (len1 > 0) : k = int((first[len1] + 1) ** 0.5); tempsuf = tempsuf + str(k); len1 = len1 - first[len1]; if (tempsuf < suffix or suf_init == False): lower = value[change]; upper = change; suffix = tempsuf; suf_init = True; # check if number is found if (found) : # construct the number from first values x = lower; for i in range(n - x): answer += '1' temp = upper; # fill in rest of the digits while (temp > 0) : dig = int((first[temp] + 1) ** 0.5); temp = temp - first[temp]; answer += str(dig); return answer; else: return "-1";# driver code# initialise NN = 2;print(minValue(N));# This code is contributed by phasing17. |
C#
// C# implementation to find the Smallest// N digit number whose sum of square// of digits is a Perfect Squareusing System;using System.Collections.Generic;class GFG { static long[] value = new long[(int)8100006]; static int[] first = new int[8100006]; // array for all possible changes static int[] coins = { 3, 8, 15, 24, 35, 48, 63, 80 }; public static void coinChange() { long inf = Int32.MaxValue; // iterating till 81 * N // since N is at max 10^5 for (int x = 1; x <= 8100005; x++) { value[x] = inf; foreach (int c in coins) { if (x - c >= 0 && value[x - c] + 1 < value[x]) { value[x] = Math.Min(value[x], value[x - c] + 1); // least value of coin first[x] = c; } } } } // function to find the // minimum possible value public static string minValue(int n) { // applying coin change for all the numbers coinChange(); string answer = ""; // check if number is // perfect square or not if ((Math.Sqrt(n) * Math.Sqrt(n)) == n) { for (int i = 0; i < n; i++) answer += "1"; return answer; } long hi = 81 * n; long lo = (long)Math.Sqrt(n); // keeps a check whether // number is found or not bool found = false; long upper = 81 * n; long lower = n; // sorting suffix strings string suffix = ""; bool suf_init = false; while ((lo * lo) <= hi) { lo++; long curr = lo * lo; long change = curr - n; if (value[(int)change] <= lower) { // build a suffix string found = true; if (lower > value[(int)change]) { // number to be used for updation of // lower, first values that will be used // to construct the final number later lower = value[(int)change]; upper = change; suffix = ""; suf_init = true; int len = (int)change; while (len > 0) { int k = (int)Math.Sqrt(first[len] + 1); suffix = suffix + (char)(k + 48); len = len - first[len]; } } else if (lower == value[(int)change]) { string tempsuf = ""; int len = (int)change; while (len > 0) { int k = (int)Math.Sqrt(first[len] + 1); tempsuf = tempsuf + (char)(k + 48); len = len - first[len]; } if ((tempsuf.CompareTo(suffix) < 0) || (suf_init == false)) { lower = value[(int)change]; upper = change; suffix = tempsuf; suf_init = true; } } } } // check if number is found if (found) { // construct the number from first values long x = lower; for (int i = 0; i < (n - x); i++) answer += "1"; long temp = upper; // fill in rest of the digits while (temp > 0) { int dig = (int)Math.Sqrt(first[(int)temp] + 1); temp = temp - first[(int)temp]; answer += (char)(dig + '0'); } return answer; } else return "-1"; } // Driver code public static void Main(string[] args) { // initialise N int N = 2; Console.WriteLine(minValue(N)); }}// This code is contributed by phasing17 |
Javascript
// JS implementation to find the Smallest// N digit number whose sum of square// of digits is a Perfect Squarelet value = new Array(8100006).fill(0);let first = new Array(8100006).fill(0);// array for all possible changeslet coins = [ 3, 8, 15, 24, 35, 48, 63, 80 ];function coinChange(){ let inf = 99999999; // iterating till 81 * N // since N is at max 10^5 for (let x = 1; x <= 8100005; x++) { value[x] = inf; for (var c of coins) { if (x - c >= 0 && value[x - c] + 1 < value[x]) { value[x] = Math.min(value[x], value[x - c] + 1); // least value of coin first[x] = c; } } }}// function to find the// minimum possible valuefunction minValue( n){ // applying coin change for all the numbers coinChange(); let answer = ""; // check if number is // perfect square or not if ( Math.floor(Math.sqrt(n)) ** 2 == n) { for (let i = 0; i < n; i++) answer += "1"; return answer; } let hi = 81 * n; let lo = Math.floor(Math.sqrt(n)); // keeps a check whether // number is found or not let found = false; let upper = 81 * n; let lower = n; // sorting suffix lets let suffix; let suf_init = false; while ((lo * lo) <= hi) { lo++; let curr = lo * lo; let change = curr - n; if (value[change] <= lower) { // build a suffix let found = true; if (lower > value[change]) { // number to be used for updation of lower, // first values that will be used // to construct the final number later lower = value[change]; upper = change; suffix = ""; suf_init = true; let len = change; while (len > 0) { let k = Math.floor(Math.sqrt(first[len] + 1)); suffix = suffix + (k).toString(); len = len - first[len]; } } else if (lower == value[change]) { let tempsuf = ""; let len = change; while (len > 0) { let k = Math.floor(Math.sqrt(first[len] + 1)); tempsuf = tempsuf + (k).toString(); len = len - first[len]; } if (tempsuf < suffix || suf_init == false) { lower = value[change]; upper = change; suffix = tempsuf; suf_init = true; } } } } // check if number is found if (found) { // construct the number from first values let x = lower; for (let i = 0; i < (n - x); i++) answer += "1"; let temp = upper; // fill in rest of the digits while (temp > 0) { let dig = Math.floor(Math.sqrt(first[temp] + 1)); temp = temp - first[temp]; answer += (dig).toString(); } return answer; } else return "-1";}// driver code// initialise Nlet N = 2;console.log(minValue(N));// This code is contributed by phasing17. |
Output:
34
Time Complexity : O(81 * N)
Auxiliary Space: O(81 * 105)
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!
