$f \left( P \right) = \sum_i \left( X_i - P \right)^2$ を最小化したいです。これを展開すると $\sum_i \left( X_i - P \right)^2 = \sum_i \left( X_i^2 - 2PX_i + P^2 \right) = \sum_i \left( X_i^2 \right) - 2 \sum_i \left( X_i \right) P + N P^2$ です。
ここで $\sum_i \left( X_i^2 \right), \sum_i \left( X_i \right)$ は $P$ によらない定数です。よってこれを $Q, R$ とすると $f \left( P \right) = NP^2 - 2RP + Q = N \left( P - \frac{R}{N} \right)^2 + Q - \frac{R^2}{N}$ となるので $f \left( P \right)$ は $P = \frac{R}{N}$ で最小値を取ります。

$R = \sum_i \left( X_i \right)$ なので $f \left( P \right)$ を最小化する $P$ は $X_i$ の平均値です。
今回の問題では $P$ は整数とする制約があるので、 $X_i$ の平均値に一番近い整数高々 $2$ つ(実際は丸めることで $1$ つにできます)のみを $P$ として調べれば良いです。

計算量は全体で \(O \left( N \right)\) です。