40_EggDropping_recursive.cpp

// T.C = O(floor * (2^min(floor, egg))
// S.C = O(1)

#include <bits/stdc++.h>
using namespace std;

int Solve(int eggs, int floors) {
	if (eggs == 0) {
		return 0;
	}
	if (eggs == 1 || floors == 0 || floors == 1) {
		return floors;
	}
	int mn = INT_MAX;
	for (int k = 1; k <= floors; k++) {
		int temp_ans = 1 + max(Solve(eggs - 1, k - 1), Solve(eggs, floors - k)); // once egg break means decrement both floor and egg another agg did not break means check egg dropping from above 
		mn = min(mn, temp_ans);
	}

	return mn;
}

int main() {
	int eggs, floors;
	cin >> eggs >> floors;

	cout << Solve(eggs, floors) << endl;
	return 0;
}