Smallest N digit number whose sum of square of digits is a Perfect Square | C ++ 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 square ; function to calculate the smallest N digit number ; place digits greater than equal to prev ; check if placing this digit leads to a solution then return it ; else backtrack ; create a string representing the N digit number ; driver code ; initialise N
#include <bits/stdc++.h> NEW_LINE using namespace std ; int isSquare ( int n ) { int k = sqrt ( n ) ; return ( k * k == n ) ; } int calculate ( int pos , int prev , int sum , vector < int > & v ) { if ( pos == v . size ( ) ) return isSquare ( sum ) ; for ( int i = prev ; i <= 9 ; i ++ ) { v [ pos ] = i ; sum += i * i ; if ( calculate ( pos + 1 , i , sum , v ) ) return 1 ; sum -= i * i ; } return 0 ; } string minValue ( int n ) { vector < int > v ( n ) ; if ( calculate ( 0 , 1 , 0 , v ) ) { string answer = " " ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) answer += char ( v [ i ] + '0' ) ; return answer ; } else return " - 1" ; } int main ( ) { int N = 2 ; cout << minValue ( N ) ; return 0 ; }