Add Golomb Sequence (fixes TheAlgorithms#2889) (TheAlgorithms#2991)

siddhant2002 · web-flow · commit 060069cf732c · 2022-04-06T19:02:30.000+03:00
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/CountFriendsPairing.java b/src/main/java/com/thealgorithms/dynamicprogramming/CountFriendsPairing.java
@@ -0,0 +1,35 @@
+/** Author : Siddhant Swarup Mallick
+ * Github : https://github.com/siddhant2002
+ */
+/**
+ * In mathematics, the Golomb sequence is a non-decreasing integer sequence where n-th term is equal to number of times n appears in the sequence.
+ */
+
+/**
+ * Wikipedia Link - https://en.wikipedia.org/wiki/Golomb_sequence
+ */
+
+/** Program description - To find the Golomb sequence upto n */
+
+package com.thealgorithms.dynamicprogramming;
+
+public class CountFriendsPairing {
+    public static boolean countFriendsPairing(int n, int a[]) {
+        int dp[] = new int[n + 1];
+        // array of n+1 size is created
+        dp[0] = 1;
+        // since 1st index position value is fixed so it's marked as 1
+        for (int i = 1; i < n; i++) {
+            dp[i] = 1 + dp[i - dp[dp[i - 1]]];
+            // formula for ith golomb sequence is dp(i) = 1 + dp(i – dp(dp(i - 1)))
+        }
+        for (int i = 1; i < n; i++) {
+            if (a[i - 1] != dp[i]) {
+                return false;
+                // checks whether the calculated answer matches with the expected answer
+            }
+        }
+        return true;
+        // returns true if calculated answer matches with the expected answer
+    }
+}
diff --git a/src/test/java/com/thealgorithms/others/CountFriendsPairingTest.java b/src/test/java/com/thealgorithms/others/CountFriendsPairingTest.java
@@ -0,0 +1,62 @@
+package com.thealgorithms.others;
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.thealgorithms.dynamicprogramming.CountFriendsPairing;
+public class CountFriendsPairingTest {
+    @Test
+	void testForOneElement() 
+	{
+        int a[] = {1,2,2};
+		assertTrue(CountFriendsPairing.countFriendsPairing(3,a));
+	}
+
+	@Test
+	void testForTwoElements() 
+	{
+        int a[] = {1,2,2,3};
+		assertTrue(CountFriendsPairing.countFriendsPairing(4,a));
+	}
+
+	@Test
+	void testForThreeElements() 
+	{
+        int a[] = {1,2,2,3,3};
+		assertTrue(CountFriendsPairing.countFriendsPairing(5,a));
+	}
+
+	@Test
+	void testForFourElements() 
+	{
+        int a[] = {1,2,2,3,3,4};
+		assertTrue(CountFriendsPairing.countFriendsPairing(6,a));
+	}
+
+	@Test
+	void testForFiveElements() 
+	{
+        int a[] = {1,2,2,3,3,4,4};
+		assertTrue(CountFriendsPairing.countFriendsPairing(7,a));
+	}
+
+	@Test
+	void testForSixElements() 
+	{
+        int a[] = {1,2,2,3,3,4,4,4};
+		assertTrue(CountFriendsPairing.countFriendsPairing(8,a));
+	}
+
+	@Test
+	void testForSevenElements() 
+	{
+        int a[] = {1,2,2,3,3,4,4,4,5};
+		assertTrue(CountFriendsPairing.countFriendsPairing(9,a));
+    }
+
+	@Test
+	void testForEightElements() 
+	{
+        int a[] = {1,2,2,3,3,4,4,4,5,5};
+		assertTrue(CountFriendsPairing.countFriendsPairing(10,a));
+	}
+}
