This article will explain how to find binary friends (binary numbers without consecutive 1s) using C++. This problem will serve as a good practice to enhance algorithm problem-solving skills.<\/p>\n<\/header>\n A binary friend refers to a binary number composed of 0s and 1s that does not have consecutive 1s. For example, 0, 1, 10, 100, 101 are binary friends. However, 11, 111, and 1100 are not. The problem is to find how many binary friends of n digits exist for a given natural number n.<\/p>\n The first line contains a natural number n (1 \u2264 n \u2264 45).<\/p>\n Output the count of binary friends with n digits.<\/p>\n<\/section>\n To solve this problem, we will utilize the properties of the Fibonacci sequence. The ways to create a binary friend can be divided as follows:<\/p>\n Therefore, the count of binary friends can be defined as follows:<\/p>\n Here, f(n) represents the count of n-digit binary friends. The initial values can be set as follows:<\/p>\n Thus, to find n binary friends, we can utilize the method of calculating the Fibonacci sequence. Now, let’s implement the actual code in C++.<\/p>\n<\/section>\n The above code is a program that calculates the count of n-digit binary friends for a given n. First, it creates a dynamic array and allocates memory setting the initial values. Then, it proceeds from 3 to n, finding the binary friends for each digit by summing the previous two terms.<\/p>\n Finally, in the main function, it takes input from the user for n and, under the appropriate conditions, outputs the count of binary friends. Do not forget to free the allocated array for memory management in any case.<\/p>\n<\/section>\n It is important to test the code after writing it. Check the results for the following input values:<\/p>\n You should confirm that the correct results are output for such inputs. It is advisable to verify by manually counting binary friends for each n value.<\/p>\n<\/section>\n In this class, we learned how to solve the binary friend problem using C++. This problem is a good example of the Fibonacci sequence and dynamic programming. You can develop your algorithm problem-solving skills through this problem, so practice with various input values.<\/p>\n<\/section>\nProblem Description<\/h2>\n
Input<\/h3>\n
Output<\/h3>\n
Approach and Solution Method<\/h2>\n
\n
f(n) = f(n-1) + f(n-2)<\/code><\/pre>\n\n
Code Implementation<\/h2>\n
\n#include <iostream>\n\nusing namespace std;\n\nlong long findBinaryFriend(int n) {\n long long *dp = new long long[n + 1];\n dp[1] = 2; \/\/ 1-digit binary friend\n dp[2] = 3; \/\/ 2-digit binary friend\n\n for (int i = 3; i <= n; i++) {\n dp[i] = dp[i - 1] + dp[i - 2];\n }\n\n return dp[n];\n}\n\nint main() {\n int n;\n cout << \"Enter a natural number n (1\u2264n\u226445): \";\n cin >> n;\n\n if (n >= 1 && n <= 45) {\n cout << n << \" digit binary friend's count is: \" << findBinaryFriend(n) << \".\" << endl;\n } else {\n cout << \"Invalid input.\" << endl;\n }\n\n return 0;\n}\n <\/code><\/pre>\nCode Explanation<\/h3>\n
Testing and Validation<\/h2>\n
\n
Conclusion<\/h2>\n