diff --git a/algorithms-modules/algorithms-numeric/src/main/java/com/baeldung/algorithms/sumoftwosquares/NumberAsSumOfTwoSquares.java b/algorithms-modules/algorithms-numeric/src/main/java/com/baeldung/algorithms/sumoftwosquares/NumberAsSumOfTwoSquares.java new file mode 100644 index 000000000000..2dbf9848efaa --- /dev/null +++ b/algorithms-modules/algorithms-numeric/src/main/java/com/baeldung/algorithms/sumoftwosquares/NumberAsSumOfTwoSquares.java @@ -0,0 +1,59 @@ +package com.baeldung.algorithms.sumoftwosquares; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +public class NumberAsSumOfTwoSquares { + + private static final Logger LOGGER = LoggerFactory.getLogger(NumberAsSumOfTwoSquares.class); + + /** + * Checks if a non-negative integer n can be written as the + * sum of two squares i.e. (a^2 + b^2) + * This implementation is based on Fermat's theorem on sums of two squares. + * + * @param n The number to check (must be non-negative). + * @return true if n can be written as a sum of two squares, false otherwise. + */ + public static boolean isSumOfTwoSquares(int n) { + if (n < 0) { + LOGGER.warn("Input must be non-negative. Returning false for n = {}", n); + return false; + } + if (n == 0) { + return true; // 0 = 0^2 + 0^2 + } + + // 1. Reduce n to an odd number if n is even. + while (n % 2 == 0) { + n /= 2; + } + + // 2. Iterate through odd prime factors starting from 3 + for (int i = 3; i * i <= n; i += 2) { + // 2a. Find the exponent of the factor i + int count = 0; + while (n % i == 0) { + count++; + n /= i; + } + + // 2b. Check the condition from Fermat's theorem + // If i is of form 4k+3 (i % 4 == 3) and has an odd exponent + if (i % 4 == 3 && count % 2 != 0) { + LOGGER.debug("Failing condition: factor {} (form 4k+3) has odd exponent {}", i, count); + return false; + } + } + + // 3. Handle the last remaining factor (which is prime if > 1) + // If n itself is a prime of the form 4k+3, its exponent is 1 (odd). + if (n % 4 == 3) { + LOGGER.debug("Failing condition: remaining factor {} is of form 4k+3", n); + return false; + } + + // 4. All 4k+3 primes had even exponents. + return true; + } +} \ No newline at end of file diff --git a/algorithms-modules/algorithms-numeric/src/test/java/com/baeldung/algorithms/sumoftwosquares/NumberAsSumOfTwoSquaresUnitTest.java b/algorithms-modules/algorithms-numeric/src/test/java/com/baeldung/algorithms/sumoftwosquares/NumberAsSumOfTwoSquaresUnitTest.java new file mode 100644 index 000000000000..ecf2f35efa9b --- /dev/null +++ b/algorithms-modules/algorithms-numeric/src/test/java/com/baeldung/algorithms/sumoftwosquares/NumberAsSumOfTwoSquaresUnitTest.java @@ -0,0 +1,47 @@ +package com.baeldung.algorithms.sumoftwosquares; + +import org.junit.jupiter.api.Test; +import org.junit.jupiter.api.DisplayName; +import static org.junit.jupiter.api.Assertions.assertTrue; +import static org.junit.jupiter.api.Assertions.assertFalse; + + +class NumberAsSumOfTwoSquaresUnitTest { + + @Test + @DisplayName("Given input number can be expressed as a sum of squares, when checked, then returns true") + void givenNumberIsSumOfSquares_whenCheckIsCalled_thenReturnsTrue() { + // Simple cases + assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(0)); // 0^2 + 0^2 + assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(1)); // 1^2 + 0^2 + assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(5)); // 1^2 + 2^2 + assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(8)); // 2^2 + 2^2 + + // Cases from Fermat theorem + assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(50)); // 2 * 5^2. No 4k+3 primes. + assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(45)); // 3^2 * 5. 4k+3 prime (3) has even exp. + assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(18)); // 2 * 3^2. 4k+3 prime (3) has even exp. + } + + @Test + @DisplayName("Given input number can't be expressed as a sum of squares, when checked, then returns false") + void givenNumberIsNotSumOfSquares_whenCheckIsCalled_thenReturnsFalse() { + // Simple cases + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(3)); // 3 (4k+3, exp 1) + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(6)); // 2 * 3 (3 has exp 1) + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(7)); // 7 (4k+3, exp 1) + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(11)); // 11 (4k+3, exp 1) + + // Cases from theorem + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(12)); // 2^2 * 3 (3 has exp 1) + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(21)); // 3 * 7 (both 3 and 7 have exp 1) + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(28)); // 2^2 * 7 (7 has exp 1) + } + + @Test + @DisplayName("Given input number is negative, when checked, then returns false") + void givenNegativeNumber_whenCheckIsCalled_thenReturnsFalse() { + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(-1)); // Negatives as hygiene + assertFalse(NumberAsSumOfTwoSquares.isSumOfTwoSquares(-10)); // Negatives as hygiene + } +}