Subtree Removal Game with Fibonacci Tree - Practice Coding Problems

Subtree Removal Game with Fibonacci Tree - Problem

Math Dynamic Programming Tree Binary Tree Game Theory Hard

A Fibonacci tree is a binary tree created using the order function order(n):

order(0) is the empty tree
order(1) is a binary tree with only one node
order(n) is a binary tree that consists of a root node with the left subtree as order(n - 2) and the right subtree as order(n - 1)

Alice and Bob are playing a game with a Fibonacci tree with Alice starting first. On each turn, a player selects a node and removes that node and its subtree. The player that is forced to delete root loses.

Given the integer n, return true if Alice wins the game or false if Bob wins, assuming both players play optimally.

A subtree of a binary tree is a tree that consists of a node in tree and all of this node's descendants. The tree could also be considered as a subtree of itself.

Input & Output

Example 1 — Small Fibonacci Tree

$ Input: n = 1

› Output: true

💡 Note: Fibonacci tree order(1) has only one node. Alice must remove it (the root) and loses. Wait, that's wrong - Alice wins because Bob is forced to remove root. Actually, with only one node, Alice removes it and wins because it's the only move.

Example 2 — Larger Tree

$ Input: n = 3

› Output: false

💡 Note: Fibonacci tree order(3) has root with left=order(1) and right=order(2). Alice can remove non-root nodes, but optimal play leads to Bob winning.

Example 3 — Pattern Example

$ Input: n = 4

› Output: true

💡 Note: Following the mathematical pattern, since 4 % 3 = 1 ≠ 0, Alice wins with optimal play.

Constraints

1 ≤ n ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Fibonacci tree order n

Game Rules

Players remove subtrees, avoiding root removal

Output

Winner with optimal play

Key Takeaway

🎯 Key Insight: Fibonacci tree games follow a mathematical pattern based on n % 3

Asked in

G Google 25 M Microsoft 18

This game theory problem on Fibonacci trees has an elegant mathematical solution. The key insight is that game outcomes follow a periodic pattern: Alice wins when n % 3 ≠ 0, Bob wins when n % 3 = 0. Best approach uses pattern recognition in O(1) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Pattern Recognition	O(1)	O(1)	Find the mathematical pattern in Fibonacci tree game outcomes
Recursive Game Simulation	O(2^n)	O(2^n)	Recursively simulate all possible moves to determine winner
Memoized Game Theory	O(2^n)	O(2^n)	Use memoization to cache game states and avoid recalculation

Mathematical Pattern Recognition — Algorithm Steps

Calculate total nodes in Fibonacci tree using formula
Determine pattern based on modular arithmetic
Return result based on mathematical rule

Visualization

Tap to expand

Step-by-Step Walkthrough

Pattern Analysis

Game outcomes follow n % 3 pattern

Mathematical Rule

Alice wins when n % 3 ≠ 0

Constant Time

Simple modular arithmetic gives answer

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool solution(int n) {
    if (n == 0) return false;
    
    // Mathematical pattern: Alice wins if n % 3 != 0
    return n % 3 != 0;
}

int main() {
    int n;
    scanf("%d", &n);
    
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Simple modular arithmetic operation

✓ Linear Growth

Space Complexity

O(1)

Only uses constant space for variables

✓ Linear Space

25.8K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler