4kyu Sums of Perfect Squares

題目背景：

The task is simply stated. Given an integer n (3 < n < 109), find the length of the smallest list of perfect squares which add up to n.

Examples:

sum_of_squares(17) = 2 17 = 16 + 1 (4 and 1 are perfect squares). sum_of_squares(15) = 4 15 = 9 + 4 + 1 + 1. There is no way to represent 15 as the sum of three perfect squares. sum_of_squares(16) = 1 16 itself is a perfect square.

題目分析：
真心感覺(jué)Codewars里面很喜歡出數(shù)學(xué)題，這道題感覺(jué)已經(jīng)不是程序的思路，就是純粹的數(shù)學(xué)問(wèn)題，依據(jù)Lagrange’s four-square 理論，任意一個(gè)正整數(shù)都可以被拆解為4個(gè)或4個(gè)以下的完美平方數(shù)之和，同時(shí)如果n = 4^k * (8 * m + 7)，那么它決不可能是3個(gè)完美正整數(shù)之和，所以就很好分析了，對(duì)于一個(gè)完美平方數(shù)或者兩個(gè)完美平方數(shù)可以直接暴力判別，只需要處理好三個(gè)或四個(gè)完美平方數(shù)之和的判斷即可。

最終AC的代碼：

#include <cmath> int sum_of_squares(int n) {int j = std::sqrt(n);if ( j * j == n ) return 1;for ( int i = 1; i * i <= n; i++ ) {int j = std::sqrt(n - i * i);if ( j * j == (n - i * i) ) return 2;}// based on Lagrange's four-square theorem, any positive integer can be written as the sum of four or fewer perfect squares.// and if n = 4^k * (8 * m + 7), it can't be 3 squares'sumwhile ( n % 4 == 0 ) n /= 4;if ( n % 8 == 7 ) return 4;return 3; }

總結(jié)

以上是生活随笔為你收集整理的4kyu Sums of Perfect Squares的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。