Divisor Game | LeetCode | C++ Easy Explanation

📌 Title: Divisor Game | LeetCode | C++ Easy Explanation

🔹 Problem: Divisor Game

🔗 LeetCode Problem:
https://leetcode.com/problems/divisor-game/

📌 Problem Explanation:

Alice and Bob are playing a game.

Initially, there is a number n written on the board.

On each turn, a player must choose a number x such that:
* n % x == 0

Then replace n with n - x.

A player loses if they cannot make a valid move.

Both Alice and Bob play optimally.

We need to determine whether Alice wins the game.

👉 Example:

Input: n = 2

Alice chooses x = 1

n becomes 1

Bob cannot make any move.

Output: true

---

💡 Approach:

After observing several examples, a pattern appears:

* If n is even, Alice can always force a win.
* If n is odd, Alice will eventually lose if Bob plays optimally.

Therefore:

* Return true when n is even.
* Return false when n is odd.

👉 Why this works:

* Choosing a divisor from an even number can always make the opponent face an odd number.
* Odd numbers only have odd divisors, which always produce an even number after subtraction.
* This creates a winning strategy for Alice whenever n is even.

---

⏱ Time Complexity:

O(1)

Only one modulo operation is performed.

💾 Space Complexity:

O(1)

No extra space is used.

---

🧠 Key Concepts:

* Mathematics
* Game Theory
* Pattern Observation
* Modulo Operator

---

📝 Notes:

* Very popular game theory problem.
* Can be solved without simulation.
* Important example of finding mathematical patterns.
* Demonstrates how observation can simplify a problem dramatically.

---

🔗 GitHub Repository:
https://github.com/abdulhaque2005

🔗 LeetCode Profile:
https://leetcode.com/u/pDjnXUuCp8/

🔗 LinkedIn:
https://www.linkedin.com/in/abdul-haque78/

---

🚀 DSA Practice Journey:

* 160+ LeetCode Questions
* 40 YouTube Videos
* C++ + STL based solutions

---

#DSA #LeetCode #CPP #Coding #Programming #Math #GameTheory

Видео Divisor Game | LeetCode | C++ Easy Explanation канала HaqueCodes