- All Contests
- ProjectEuler+
- Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square
- Discussions

# Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square

# Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square

degodoy + 1 comment Well, the example is crazy completely different from what he wants. It leads you to think that se answer is f(100) = 1^2 + 0^2 + 0^2 based on the question input. I believe itÂ´s an easy level but the explanation is hard.

mangist + 1 comment what is the real question then? What should the output be?

raghav3a + 0 comments You have to consider all integers between 0 to k (both inclusive) that show a property like:

f(n) = sum of squares of digits of n = a perfect square

Example: f(100) = 1^2 + 0^2 + 0^2 = 1 => A perfect square. So add 100 to your overall sum

f(101) = 1^2 + 0^2 + 1^2 = 2 => Not a perfect sqaure. So leave it.

Continue in such way for n in [0,k] and sum for all such n.

Hope that helps!

danishnayyar05 + 0 comments actual question says perfect square moduli(10^9+7)

jcisio + 0 comments This is much harder than the original question. I can solve the original question in 3 seconds (Python 3), but the following changes make it much much harder:

- n could be 10^100 instead of 10^20 (at 10^20 I'm at 3s, the sum is about 10^40, at 10^30 I'm at 50s and I didn't bother testing more).
- n could be other than 10^N (e.g. n = 12563) makes me use a second algorithm

The extra "module 10^9 + 1" is just a diversion. In the range of n <= 10^100 they are just perfect squares (the next one is 14122 = 31623^2 module 10^9 + 1 but it has at least 175 digits).

ankushbindlish + 1 comment Let me try to explain the problem and reach out to 826 from 100

Givem k=100 , 0<=n<=100 Iterate n, for n = 0 to 100 if(f(n) is a perfect square) add to the result

(Please sum to get 826) 0 1 2 3 4 5 6 7 8 9 10 20 30 34 40 43 50 60 68 70 80 86 90 100

Naive solution: static void Main(string[] args) { long k = 100; long output = Project_Euler_171(k); }

`private static long Project_Euler_171(long k) { long sum = 0; for(int i = 0; i <= k; i++) { sum += IsPowerSquare(f(i)) ? i : 0; } return sum; } private static bool IsPowerSquare(long n) { double number = (double)n; return ((double)(Math.Sqrt(number) - (long)Math.Sqrt(number))) == 0.0; } private static long f(long n) { if (n == 0) return 0; return f(n / 10) + (n % 10) * (n % 10); }`

kbosak + 1 comment "Given k=100" Is this a joke? The author asked for a code valid for k<=10^100, not k<=100.

ankushbindlish + 0 comments kbosak, This explaination was to explain output 826 from given input 100 and does not cover the number range problem of k. Hope it helps. Thanks.

Abdesk + 0 comments what's the error in it can anyone tell that...

//Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square #include<iostream> #include<math.h> using namespace std; bool isPerfectSquare(long double x) { // Find floating point value of // square root of x. long double sr = sqrt(x); // If square root is an integer return ((sr - floor(sr)) == 0); } int main(){ unsigned long int range=0100,sum=0,rem=0,bsum=0,lo=0; cin>>range; unsigned long int hold; for(int i=1;i<=range;i++){ hold=i; while(hold>0){ rem=hold%10; hold/=10; sum+=rem*rem; lo+=sum; sum=0; } if (isPerfectSquare(lo)){ bsum+=i; } lo=0; } cout<<bsum; }

ankitsorathiya + 1 comment Very confusing discription, Can it be made little simple to understand?

abhi3008 + 0 comments Read the heading again

angeloruocco90 + 1 comment Given the constraint k<10^100 a O(n) algorithm is not a viable solution, no matter the optimizations.

Another idea is to check all the unique combinations (combinations with repetitions) of digits, and then add the permutations of that number to the total if found to be a perfect square (and less than k).

Es. 3 digits: 001, 010 and 100 are the same, and so are 123, 132, 213, 231, 312, 321. With checking one of them you know all the others, whether they are a perfect square or not.

But, brute-force searching to all the possible unique combinations for 100 digits would have a cost of: (10 + 100 - 1)! / (100! * (10-1)!) ~ 10^12, less than 10^100, but still not at all feasible.

EDIT: Nevermind, forgot the cost of the permutations.

EDIT2: Even without the cost of the permutations, just looping through all the possibile digits alternatives and checking if one is a perfect square or not, I got timeout for 15/19 of the test cases.

There must be some way to know those square numbers, or the correct guess of the sum, in advance.

mdmushtaq007 + 0 comments Nice analysis. And i am still figuring out, how to process the input k (10^100), even wondering can i use "C" for this?

ankitkundu1602 + 0 comments I have written the following code:

# include

# include

int main() { float check; int i, r, ex, k, s, result=0; scanf("%d",&k); for(i=1; i<=k ; i++) { ex=i; s=0; while(i>0) { r=i%10; s=s+(r*r); i=i/10; } check=(int)(sqrt(s)); if((sqrt(s)-check)==0) result=result+ex;

} printf("%d",result);`return 0;`

}

Each time I rum the code, it says time-out but I cannot make this any smaller. Some one please give some suggestion.

mridsmighty1 + 3 comments Please review my code ,it is showing run time error an i am not able to solve it.

import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution {

`public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); int q=0,f=0; double d=0,ans=0; outer: for(int i=1;i<=t;i++) { int s=0; for(int j=i;j>0;j=j/10) { f=j%10; f=f*f; s=s+f; } double r=Math.sqrt(s); q=(int)r; d=r-q; if(d==0) ans=ans+i; else continue outer; } System.out.println(ans); }`

}

TheMentor + 0 comments I think you hit the RuntimeError because you gave into input bigger number that is possible to store into value of int. But it's only my opinion.

mangist + 0 comments I had runtime errors too, it's related to your data type not able to handle up to the required Input Constraint of 1e-100 (10 ^ 100). That is a huge number. I had to use a special BigInteger class in C#. Also, I have 4 test cases passing, but the rest timeout (3 seconds). My algorithm is O(n), which is obviously too slow for a loop on an input k such as 100,000,000,000,000,000,000.

aviroopbasu2017 + 0 comments Analyze ur complexity. See the constraints

Sort 67 Discussions, By:

Please Login in order to post a comment