C++ Coding Test Course, Finding Incomplete Numbers

Problem Description

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.

Input

The first line contains a natural number n (1 ≤ n ≤ 45).

Output

Output the count of binary friends with n digits.

Approach and Solution Method

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:

• If the leftmost bit of the n-digit binary friend is 0, the remaining bits become (n-1)-digit binary friends.
• If the leftmost bit of the n-digit binary friend is 1, the next bit must be 0, thus the remaining bits will become (n-2)-digit binary friends.

Therefore, the count of binary friends can be defined as follows:

f(n) = f(n-1) + f(n-2)

Here, f(n) represents the count of n-digit binary friends. The initial values can be set as follows:

• f(1) = 2 (0, 1)
• f(2) = 3 (00, 01, 10)

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++.

Code Implementation

#include <iostream>

using namespace std;

long long findBinaryFriend(int n) {
    long long *dp = new long long[n + 1];
    dp[1] = 2; // 1-digit binary friend
    dp[2] = 3; // 2-digit binary friend

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    cout << "Enter a natural number n (1≤n≤45): ";
    cin >> n;

    if (n >= 1 && n <= 45) {
        cout << n << " digit binary friend's count is: " << findBinaryFriend(n) << "." << endl;
    } else {
        cout << "Invalid input." << endl;
    }

    return 0;
}
            

Code Explanation

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.

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.

Testing and Validation

It is important to test the code after writing it. Check the results for the following input values:

• n = 1: Result is 2 (0, 1)
• n = 2: Result is 3 (00, 01, 10)
• n = 3: Result is 5 (000, 001, 010, 100, 101)
• n = 4: Result is 8
• n = 5: Result is 13

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.

Conclusion

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.