Solution

import java.util.LinkedList; import java.util.Queue; public class Game { static class Pos { int index; int k; Pos(int index, int k) { this.index = index; this.k = k; } } public static void main(String[] args) { // TODO Auto-generated method stub int n = 2; // N Queue<Pos> q = new LinkedList<>(); q.add(new Pos(0, 1)); int result = 0; boolean canReachN = false; while(!q.isEmpty()) { Pos head = q.poll(); if(head.index == n) { // check if is win or not canReachN = true; result = head.k - 1; break; } int k_new = head.k + 1; int index_newRight = head.index + head.k; int index_newLeft = head.index - head.k; if(Math.abs(n - index_newRight) <= k_new) q.add(new Pos(index_newRight, k_new)); if(Math.abs(n - index_newLeft) <= k_new)q.add(new Pos(index_newLeft, k_new)); } if(canReachN) System.out.println(result); else System.out.println("Cant win"); } }