Perimeter of squares in a rectangle in Java

The challenge

The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It’s easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80

Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing:

Hint: See Fibonacci sequence

Ref:

http://oeis.org/A000045

The function perimeter has for parameter n where n + 1 is the number of squares (they are numbered from 0 to n) and returns the total perimeter of all the squares.

perimeter(5) should return 80 perimeter(7) should return 216
Code language: JavaScript (javascript)

The solution in Java code

Option 1:

import java.math.BigInteger; public class SumFct { public static BigInteger perimeter(BigInteger n) { BigInteger a = BigInteger.ZERO; BigInteger b = BigInteger.ONE; BigInteger c = BigInteger.ONE; BigInteger sum = BigInteger.ZERO; for(int i = 0; i <= n.intValue(); i++) { a = b; b = c; c = a.add(b); sum = sum.add(a); } return sum.multiply(BigInteger.valueOf(4)); } }
Code language: Java (java)

Option 2:

import java.math.BigInteger; public class SumFct { public static BigInteger perimeter(BigInteger n) { BigInteger a = BigInteger.ZERO; BigInteger b = BigInteger.ONE; BigInteger c = BigInteger.ONE; BigInteger sum = BigInteger.ZERO; for(int i = 0; i <= n.intValue(); i++) { a = b; b = c; c = a.add(b); sum = sum.add(a); } return sum.multiply(BigInteger.valueOf(4)); } }
Code language: Java (java)

Option 3:

import java.math.BigInteger; public class SumFct { public static BigInteger perimeter(BigInteger n) { BigInteger fibSum = BigInteger.ONE; BigInteger previousFibValue = BigInteger.ZERO; BigInteger currentFibValue = BigInteger.ONE; for (BigInteger i = BigInteger.ONE; i.compareTo(n) < 1; i = i.add(BigInteger.ONE)) { currentFibValue = currentFibValue.add(previousFibValue); previousFibValue = currentFibValue.subtract(previousFibValue); fibSum = fibSum.add(currentFibValue); } return fibSum.multiply(BigInteger.valueOf(4)); } }
Code language: Java (java)

Test cases to validate our solution

import static org.junit.Assert.*; import java.math.BigInteger; import java.util.HashMap; import java.util.Random; import org.junit.Test; public class SumFctTest { private static HashMap<BigInteger, BigInteger> cache = new HashMap<BigInteger, BigInteger>(); private static BigInteger ONE = BigInteger.ONE; private static BigInteger ZERO = BigInteger.ZERO; public static BigInteger fib(BigInteger n) { if (n.equals(ZERO)) return ZERO; if (n.equals(ONE)) return ONE; if (cache.containsKey(n)) return cache.get(n); // odd if (n.testBit(0)) { BigInteger n2 = n.shiftRight(1); BigInteger n3 = n2.add(ONE); BigInteger result = fib(n2).multiply(fib(n2)).add(fib(n3).multiply(fib(n3))); cache.put(n, result); return result; } // even else { BigInteger n2 = n.shiftRight(1); BigInteger n3 = n2.subtract(ONE); BigInteger result = fib(n2).multiply(fib(n2).add(fib(n3).add(fib(n3)))); cache.put(n, result); return result; } } public static BigInteger solution(BigInteger n) { return (fib(n.add(BigInteger.valueOf(3))).subtract(BigInteger.valueOf(1))).multiply(BigInteger.valueOf(4)); } @Test public void test1() { assertEquals(BigInteger.valueOf(80), SumFct.perimeter(BigInteger.valueOf(5))); } @Test public void test2() { assertEquals(BigInteger.valueOf(216), SumFct.perimeter(BigInteger.valueOf(7))); } @Test public void test3() { assertEquals(BigInteger.valueOf(14098308), SumFct.perimeter(BigInteger.valueOf(30))); } @Test public void test4() { BigInteger r = new BigInteger("6002082144827584333104"); assertEquals(r, SumFct.perimeter(BigInteger.valueOf(100))); } @Test public void test5() { BigInteger r = new BigInteger("2362425027542282167538999091770205712168371625660854753765546783141099308400948230006358531927265833165504"); assertEquals(r, SumFct.perimeter(BigInteger.valueOf(500))); } @Test public void test6() { System.out.println("****** Random test ******"); Random rnd = new Random(); for (int i = 0; i < 25; i++) { int a = Math.round(rnd.nextInt(1000) * (65 - 10) + 10000); System.out.println("Perimeter for : " + a); assertEquals(SumFctTest.solution(BigInteger.valueOf(a)), SumFct.perimeter(BigInteger.valueOf(a))); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments