CareerCup

package Linkedin;

import java.util.List;
import java.util.ArrayList;

public class The100Game{
	List<Integer> pool;
	int raceTo;
	
	The100Game(int poolMax, int finalSum){
		if(finalSum > ((poolMax*poolMax + poolMax)/2)){
			throw new IllegalArgumentException("Expected sum cannot be achieved!");
		}
		
		raceTo = finalSum;
		pool = new ArrayList<Integer>();
		
		for(int i=0;i<poolMax;i++)
			pool.add(i+1);
	}
	
	boolean canIWin(){
		int turns = 0;
		while(raceTo>0){
			turns++;
			System.out.println("Player"+( (turns%2==0)?"2":"1" )+" ==> "+pickANumber()+"   == Remaining ["+raceTo+"]");
		}
		return (turns%2==1);
	}
	
	int pickANumber(){
		int leastMax = -1;
		int len = pool.size();
		for(int i=len-1;i>=0;i--){
			int tmp = pool.get(i);
			if(tmp>=raceTo){
				pool.remove(i);
				raceTo -= tmp;
				return tmp;	
			}else{
				if(leastMax > 0){
					if(tmp < leastMax){
						pool.remove(i);
						raceTo -= tmp;
						return tmp;
					}else{
						continue;
					}
				}	
					
				if(i-1 >= 0) {
					if(tmp+pool.get(i-1) < raceTo){
						pool.remove(i);
						raceTo -= tmp;
						return tmp;
					}else{
						leastMax = raceTo - tmp;
						i--;
						continue;
					}
				}else{
					pool.remove(i);
					raceTo -= tmp;
					return tmp;
				}
			}
		}
		
		int tmp = pool.get(pool.size()-1);
		pool.remove(pool.size()-1);
		raceTo -= tmp;
		return tmp;
	}
	
	public static void main(String[] args){
		The100Game game = new The100Game(15, 100);
		System.out.println("\nPlayer-"+(game.canIWin()?"1":"2")+" wins!");
	}
}

Answer:
Please try to solve this by yourself before seeing my solution in 1/2 hour only.

Screwed up this one big time. No help came from interviewer for proceeding on the solution. In the interview, I was thinking that it may have some recursive / dynamic programming solution. I guess, I was stumped to even grasp it at first.

Tried to discuss an example with interviewer.
// canIWin(2, 3)

I think I got confused by his inputs, as he suggested that optimum play by Player A not necessarily means that he will win if he chooses the highest available number.

Anyhow, I stumped and couldn't proceed much. Horrific.

Solution: Now i gave myself half an hour to solve this question by myself after the interview. Here is my approach.
According to me, The optimal play from player A will always have a first advantage of selecting the largest number
So e.g, for N = 10 , he may select 10, 8 , 6 , 4

Boolean canIWin(int maxChoosableInteger, int desiredTotal) {
  // Implementation here.

	int is_even=false;
	int optimumPossibleSum = 0;
	boolean status = false;

	int n = (maxChoosableInteger- 2)/2 + 1;

	if ( (maxChoosableInteger % 2) == 0 )
	{
		isEven = true;
	}

	if ( isEven )	
	{
		
		optimumPossibleSum = n * ( n + 1 );
	}

	else
	{
		optimumPossibleSum = n * n;
	}

	if ( optimumPossibleSum >= desiredTotal )
		status = true;

	return status;

}

I think this can be solved with a simple recursive algorithm. A cursory analysis suggests that the upper bound on complexity is O(n!) where n is the max choosable integer.

boolean canIWin(int maxChoosableInteger, int desiredTotal) {
		int[] numbers = new int[maxChoosableInteger];
		for (int i = 0; i < maxChoosableInteger; ++i) {
			numbers[i] = i + 1;
		}
		return canWin(numbers, desiredTotal);
	}

	boolean canWin(int[] numbers, int desiredTotal) {
		for(int i = 0; i < numbers.length; ++i) {
			int newTotal = desiredTotal - numbers[i];
			if (newTotal > 0) {
				if (!canWin(remove(numbers, i), newTotal)) {
					return true;
				}
			}
		}
		return false;
	}

	int[] remove(int[] a, int k) {
		int[] b = new int[a.length-1];
		for (int i = 0, j = 0; i < a.length; i++) {
			if (i != k) {
				b[j++] = a[i];
			}
		}
		return b;
	}

You'd probably have to do some rather advanced game theory to come up on the spot with an algorithm that better than O(n!). Either way, it's pretty well known that choosing simply the maximum number is incorrect.

This should be solvable with the following, took me closer to an hour to get it to print some valid answers despite it being 15 lines:

def canIWin(integers, total=0, turn=0):
  possibilities = []
  for i in integers:
    if total + i >= 6: # 6 is the total sum the players are trying to get
      return turn % 2 # 0 if 1st player wins, 1 if second
    else:
      ints = integers[:]
      ints.remove(i)
      winnable = canIWin(ints, total + i, turn + 1)
      possibilities.append(winnable)
  if turn % 2 == 0:
    return min(possibilities)
  return max(possibilities)

print canIWin(range(1,5)) # give as argument the available numbers

My solution is based on the assumption that both p1 and p2 are extremely smart and they will choose an optimal move to win whenever they have chance.

boolean canIWin(int maxChoosableInteger, int desiredTotal) { 
		
		boolean[] pool = new boolean[maxChoosableInteger];
		
		for(int i = 0; i<maxChoosableInteger; i++){
			pool[i] = true;
			if(canP1Win(i+1, desiredTotal, pool, true)) return true;
			pool[i] = false;
		}
		
		return false;
	}
	
	
	// Overall heuristics : canP1Win is a method that tells us whether by making this move p1 will win. 
	// and we assume both p1 and p2 are extremely smart and therefore will choose an optimal move to maximize their chances to win.
	
	// If the above statement is true, then the following is true:
	// 1. if p1 can find a way to win she will choose it
	// 2. if p2 can find a way to make p1 loose, she will choose it
	//   Therefore in order for p1 to win, such way must not exist.
	
	boolean canP1Win(int currentSum, int total, boolean[] pool, boolean isLastP1){
		
		//base case : someone did the final move, if it's p1 then she wins, otherwise she looses.
		if(currentSum >= total) return isLastP1;
		
		//recursion : game continues
		boolean isCurrentPlayerP1 = !isLastP1;
		for(int i = 0; i<pool.length; i++){
			
			if(pool[i]) continue;
			
			pool[i] = true;
			boolean p1CanWin = canP1Win(currentSum + (i+1), total, pool, isCurrentPlayerP1);
			
			//1. if p1 can find a way to win she will choose it
			if(isCurrentPlayerP1 && p1CanWin) return true;
			//2. if p2 can find a way to make p1 loose, she will choose it
			//   Therefore in order for p1 to win, such way must not exist.
			if(!isCurrentPlayerP1 && !p1CanWin) return false;
			
			// neither of the conditions above is satisfied, both player will try to pick another number that maximize their chances to win.
			pool[i] = false;
		}
		
		// player at this round has tried all possible moves:
		// 1.if it's p1's turn and she couldn't find any way to win, then she looses
		// 2.if it's p2's turn and she couldn't find any way to make p1 loose, p1 wins.
		return isCurrentPlayerP1? false : true;
	}

public class pickNumber {
public static boolean canIWin (int maxNumber, int target) {
return canIWin(maxNumber, target, new int[2], 0, new boolean[maxNumber]);
}
public static boolean canIWin(int maxNumber, int target, int[] players, int times, boolean[] visited) {
int count = 0;
for(boolean b : visited) {
if(!b) count++;
}
if(count == 0) return false;
if(times % 2 == 0) {
for(int i = 1; i <= maxNumber; i++) {
if(!visited[i - 1]) {
visited[i - 1] = true;
players[0] += i;
if(players[0] >= target || canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[0] -= i;
}
}
}
else {
for(int i = 1; i <= maxNumber; i++) {
boolean b = false;
if(!visited[i - 1] && players[1] + i < target) {
b = true;
visited[i - 1] = true;
players[1] += i;
if(canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[1] -= i;
}
if(!b) return false;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(canIWin(3, 3));
System.out.println(canIWin(3, 4));
System.out.println(canIWin(3, 5));
System.out.println(canIWin(3, 6));
}
}

public class pickNumber {
public static boolean canIWin (int maxNumber, int target) {
return canIWin(maxNumber, target, new int[2], 0, new boolean[maxNumber]);
}
public static boolean canIWin(int maxNumber, int target, int[] players, int times, boolean[] visited) {
int count = 0;
for(boolean b : visited) {
if(!b) count++;
}
if(count == 0) return false;
if(times % 2 == 0) {
for(int i = 1; i <= maxNumber; i++) {
if(!visited[i - 1]) {
visited[i - 1] = true;
players[0] += i;
if(players[0] >= target || canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[0] -= i;
}
}
}
else {
for(int i = 1; i <= maxNumber; i++) {
boolean b = false;
if(!visited[i - 1] && players[1] + i < target) {
b = true;
visited[i - 1] = true;
players[1] += i;
if(canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[1] -= i;
}
if(!b) return false;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(canIWin(3, 3));
System.out.println(canIWin(3, 4));
System.out.println(canIWin(3, 5));
System.out.println(canIWin(3, 6));
}
}

public class pickNumber {
public static boolean canIWin (int maxNumber, int target) {
return canIWin(maxNumber, target, new int[2], 0, new boolean[maxNumber]);
}
public static boolean canIWin(int maxNumber, int target, int[] players, int times, boolean[] visited) {
int count = 0;
for(boolean b : visited) {
if(!b) count++;
}
if(count == 0) return false;
if(times % 2 == 0) {
for(int i = 1; i <= maxNumber; i++) {
if(!visited[i - 1]) {
visited[i - 1] = true;
players[0] += i;
if(players[0] >= target || canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[0] -= i;
}
}
}
else {
for(int i = 1; i <= maxNumber; i++) {
boolean b = false;
if(!visited[i - 1] && players[1] + i < target) {
b = true;
visited[i - 1] = true;
players[1] += i;
if(canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[1] -= i;
}
if(!b) return false;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(canIWin(3, 3));
System.out.println(canIWin(3, 4));
System.out.println(canIWin(3, 5));
System.out.println(canIWin(3, 6));
}
}

public class pickNumber {
public static boolean canIWin (int maxNumber, int target) {
return canIWin(maxNumber, target, new int[2], 0, new boolean[maxNumber]);
}
public static boolean canIWin(int maxNumber, int target, int[] players, int times, boolean[] visited) {
int count = 0;
for(boolean b : visited) {
if(!b) count++;
}
if(count == 0) return false;
if(times % 2 == 0) {
for(int i = 1; i <= maxNumber; i++) {
if(!visited[i - 1]) {
visited[i - 1] = true;
players[0] += i;
if(players[0] >= target || canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[0] -= i;
}
}
}
else {
for(int i = 1; i <= maxNumber; i++) {
boolean b = false;
if(!visited[i - 1] && players[1] + i < target) {
b = true;
visited[i - 1] = true;
players[1] += i;
if(canIWin(maxNumber, target, players, times + 1, visited)) return true;
visited[i - 1] = false;
players[1] -= i;
}
if(!b) return false;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(canIWin(3, 3));
System.out.println(canIWin(3, 4));
System.out.println(canIWin(3, 5));
System.out.println(canIWin(3, 6));
}
}

A similar version is the "100 game": two players start from 0 and alternatively add a number from 1 to 10 to the sum. The player who reaches 100 wins. The winning strategy is to reach a number in which the digits are subsequent (e.g. 01, 12, 23, 34,...) and control the game by jumping through all the numbers of this sequence. Once reached 89, the opponent has lost (he can only tell numbers from 90 to 99, and the next answer can in any case be 100).

What about such approach:
As the main constraint is a programmer efficiency, we could just estimate for an each choice of the next number the probability of win, i.e. count the number of ways through recursion leading to our win (A) and to our fail (B). The estimation would be A/(A+B). So the optimal strategy by definition is to choose the next number with the highest probability of winning. Then we just calculate who will win with such strategy (who will pick the last possible number) and return True if the winner is the first player.
Basically it's just super-mega-bruteforce with factorial complexity but it's relatively easy to code. Just a thought, maybe will code it some time. :)

Wouldn't the player 1 always win if he picks the highest available no in the pool. Am i missing something here?

public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

		boolean candidates[] = new boolean[maxChoosableInteger];
		for (int i = 0; i < candidates.length; ++i) {
			candidates[i] = true;
		}

		return canWinHelper(candidates, desiredTotal);
	}

	private boolean canWinHelper(boolean candidates[], int total) {

		if (total <= 0) {
			return false;
		}

		boolean result = false;
		for (int i = 0; i < candidates.length; ++i) {
			// I pick, just win one
			if (candidates[i]) {
				candidates[i] = false;
				int curTotal = total - i - 1;
				if(curTotal == 0) {
					System.out.println("return");
					return true;
				}
				// the other player pick: any possibility
				// need to win all these
				boolean cur = true;
				for(int j = 0; j < candidates.length; ++j) {
					if(candidates[j]) {
					
						candidates[j] = false;
						cur = cur && canWinHelper(candidates, curTotal - j - 1);
						candidates[j] = true;
						
					}
				}
				result = result || cur;
				candidates[i] = true;
			}
		}
		return result;
	}

In this problem three results are possible:
(1) First player wins.
(2) Second player wins.
(3) No winner.

Lets define two recursive functions:
(1) CanWin(int destNumber)
(2) IsLost(int destNumber)

Also because numbers in range 1-N are not re-usable we should hold boolean array with states. From here implementation in very simple. I coded it in C++.

bool CanWin(int destNumber);
bool IsLost(int destNumber);

vector<bool> isAvailable;
bool CanIWin(int maxChoosableInteger, int desiredTotal)
{
	//Initially all integers are available.
	isAvailable.resize(maxChoosableInteger, true);
	return CanWin(desiredTotal);
}

bool CanWin(int destNumber)
{
	for (int i=isAvailable.size()-1; i>=0; i--)
	{
		int num = i+1;

		if (!isAvailable.at(i))
			continue;

		if (destNumber <= num)
			return true;

		isAvailable.at(i) = false;
		bool isOpponentLost = IsLost(destNumber - num);
		isAvailable.at(i) = true;

		if (isOpponentLost)
			return true;
	}

	return false;
}

bool IsLost(int destNumber)
{
	for (int i=isAvailable.size()-1; i>=0; i--)
	{
		int num = i+1;

		if (!isAvailable.at(i))
			continue;

		if (destNumber <= num)
			return false;

		isAvailable.at(i) = false;
		bool canOpponentWin = CanWin(destNumber - num);
		isAvailable.at(i) = true;

		if (canOpponentWin)
			return true;
	}

	return false;
}

Is this correct simple solution? Please help explain

#include <iostream>
using namespace std;


bool canIWin(int maxChoosableInteger, int desiredTotal);

int main() {
	// your code goes here
	bool result = false;
	

	cout<<"canIwin(3,2) : "<<canIWin(3, 2)<<endl;
	cout<<"canIwin(3,3) : "<<canIWin(3, 3)<<endl;
	cout<<"canIwin(3,5) : "<<canIWin(3, 5)<<endl;
	
	return 0;
}


bool canIWin(int maxChoosableInteger, int desiredTotal) {
  // Implementation here.

	bool isEven=false;
	int optimumPossibleSum = 0;
	bool status = false;

	int n = (maxChoosableInteger + 1 - 2)/2 + 1;

	if ( (maxChoosableInteger % 2) == 0 )
	{
		isEven = true;
	}

	if ( isEven )	
	{
		
		optimumPossibleSum = n * ( n + 1 );
	}

	else
	{
		optimumPossibleSum = n * n;
	}

	if ( optimumPossibleSum >= desiredTotal )
		status = true;

	return status;

}

In 100 game, the player add number from 1... 10. the first player can force to win by always be the one reach number 1, 12, 23, 34, 45, 56, 67, 78, 89, 100.
The first player can pick 1 first. and whatever number n second player picked, the first player always pick 11-n next. That will guarantee first player to win.
So the function canIWin() shall return true as long as the 1...n can sum up to desired total.

In the modified game that number can not be reused. then there is not guarantee first player to win. But there still strategy allow the first player to win in OPTIMAL play.
for example, 1...15 and desired total is 100. In an optimal play, the first player can be the one reach 4, 20, 36, 52, 68, 84, 100.
the first player can pick 4 first. And then second player always pick the number n satisfy (n != 8 && n != 12) in an optimal play. Which give a chance for first player to pick 16-n next and eventually first player win.
for this game canIWin() can return true when following 2 conditions are satisfied:
1. 1..n can sum up to desire total.
2. desire total / (1+n) < (n/2 - 1).
after first player pick the necessary number (4), there is enough pairs (n and 16-n) left to build the desire total.

This is basically brute force, but perhaps the algorithm is clear.

using System;
using System.Collections.Generic;

namespace SumGame
{
	class Program
	{
		static void Main()
		{
		}
	}

	static class WinComputer
	{
		static bool canIWin(int maxChoice, int winTotal)
		{
			Scenario.maxChoice = maxChoice;
			Scenario.winTotal = winTotal;

			return recursiveCanPlayerAWin(new Scenario(0,0));
		}

		static bool recursiveCanPlayerAWin(Scenario scenario)
		{
			if(scenario.PlayerAHasWinningChoice())
				return true;

			for(int i = 0; i <= maxChoice; i++)
			{
				if(scenario.IsInvalidChoice(i))
					continue;

				scenario.PlayerAChoose(i);

				if(scenario.PlayerBHasWinningChoice())
					return false;

				for(int j = 0; j <= maxChoice; j++)
				{
					if(scenario.IsInvalidChoice(j))
						continue;

					Scenario branch = scenario.Clone();
					branch.PlayerBChoose(j);
					scenario.PlayerAHasWinningStrategy |= recursiveCanPlayerAWin(branch);
				}
			}

			return scenario.PlayerAHasWinningStrategy;
		}
	}

	class Scenario
	{
		public int PlayerATotal;
		public int PlayerBTotal;
		public HashSet<int> InvalidChoices;
		public bool PlayerAHasWinningStrategy;

		private static int maxChoice;
		private static int winTotal;

		public Scenario(int a, int b, HashSet<int> h = null)
		{
			PlayerATotal = a;
			PlayerBTotal = b;
			InvalidChoices = h ?? new HashSet<int>();
			PlayerAHasWinningStrategy = false;
		}

		public Scenario Clone()
		{
			return new Scenario(PlayerATotal, PlayerBTotal, InvalidChoices);
		}

		public void PlayerAChoose(int x)
		{
			PlayerATotal += x;
			InvalidChoices.Add(x);
		}

		public void PlayerBChoose(int x)
		{
			PlayerBTotal += x;
			InvalidChoices.Add(x);
		}

		public bool PlayerAHasWinningChoice()
		{
			return PlayerHasWinningChoice(PlayerATotal);
		}

		public bool PlayerBHasWinningChoice()
		{
			return PlayerHasWinningChoice(PlayerBTotal);
		}

		public bool IsInvalidChoice(int x)
		{
			return InvalidChoices.Contains(x);
		}

		public bool PlayerHasWinningChoice(int playerTotal)
		{
			for(int i = 0; i <= Scenario.maxChoice; i++)
			{
				if(!IsInvalidChoice(i) && (playerTotal + i >= Scenario.winTotal))
					return true;
			}

			return false;
		}
	}
}

This is basically brute force, but the algorithm should be clear.

using System;
using System.Collections.Generic;

namespace SumGame
{
	class Program
	{
		static void Main()
		{
		}
	}

	static class WinComputer
	{
		static bool canIWin(int maxChoice, int winTotal)
		{
			Scenario.maxChoice = maxChoice;
			Scenario.winTotal = winTotal;

			return recursiveCanPlayerAWin(new Scenario(0,0));
		}

		static bool recursiveCanPlayerAWin(Scenario scenario)
		{
			if(scenario.PlayerAHasWinningChoice())
				return true;

			for(int i = 0; i <= maxChoice; i++)
			{
				if(scenario.IsInvalidChoice(i))
					continue;

				scenario.PlayerAChoose(i);

				if(scenario.PlayerBHasWinningChoice())
					return false;

				for(int j = 0; j <= maxChoice; j++)
				{
					if(scenario.IsInvalidChoice(j))
						continue;

					Scenario branch = scenario.Clone();
					branch.PlayerBChoose(j);
					scenario.PlayerAHasWinningStrategy |= recursiveCanPlayerAWin(branch);
				}
			}

			return scenario.PlayerAHasWinningStrategy;
		}
	}

	class Scenario
	{
		public int PlayerATotal;
		public int PlayerBTotal;
		public HashSet<int> InvalidChoices;
		public bool PlayerAHasWinningStrategy;

		private static int maxChoice;
		private static int winTotal;

		public Scenario(int a, int b, HashSet<int> h = null)
		{
			PlayerATotal = a;
			PlayerBTotal = b;
			InvalidChoices = h ?? new HashSet<int>();
			PlayerAHasWinningStrategy = false;
		}

		public Scenario Clone()
		{
			return new Scenario(PlayerATotal, PlayerBTotal, InvalidChoices);
		}

		public void PlayerAChoose(int x)
		{
			PlayerATotal += x;
			InvalidChoices.Add(x);
		}

		public void PlayerBChoose(int x)
		{
			PlayerBTotal += x;
			InvalidChoices.Add(x);
		}

		public bool PlayerAHasWinningChoice()
		{
			return PlayerHasWinningChoice(PlayerATotal);
		}

		public bool PlayerBHasWinningChoice()
		{
			return PlayerHasWinningChoice(PlayerBTotal);
		}

		public bool IsInvalidChoice(int x)
		{
			return InvalidChoices.Contains(x);
		}

		public bool PlayerHasWinningChoice(int playerTotal)
		{
			for(int i = 0; i <= Scenario.maxChoice; i++)
			{
				if(!IsInvalidChoice(i) && (playerTotal + i >= Scenario.winTotal))
					return true;
			}

			return false;
		}
	}
}

This is basically brute force, but the algorithm should be clear.

using System;
using System.Collections.Generic;

namespace SumGame
{
	class Program
	{
		static void Main()
		{
		}
	}

	static class WinComputer
	{
		static bool canIWin(int maxChoice, int winTotal)
		{
			Scenario.maxChoice = maxChoice;
			Scenario.winTotal = winTotal;

			return recursiveCanPlayerAWin(new Scenario(0,0));
		}

		static bool recursiveCanPlayerAWin(Scenario scenario)
		{
			if(scenario.PlayerAHasWinningChoice())
				return true;

			for(int i = 0; i <= maxChoice; i++)
			{
				if(scenario.IsInvalidChoice(i))
					continue;

				scenario.PlayerAChoose(i);

				if(scenario.PlayerBHasWinningChoice())
					return false;

				for(int j = 0; j <= maxChoice; j++)
				{
					if(scenario.IsInvalidChoice(j))
						continue;

					Scenario branch = scenario.Clone();
					branch.PlayerBChoose(j);
					scenario.PlayerAHasWinningStrategy |= recursiveCanPlayerAWin(branch);
				}
			}

			return scenario.PlayerAHasWinningStrategy;
		}
	}

	class Scenario
	{
		public int PlayerATotal;
		public int PlayerBTotal;
		public HashSet<int> InvalidChoices;
		public bool PlayerAHasWinningStrategy;

		private static int maxChoice;
		private static int winTotal;

		public Scenario(int a, int b, HashSet<int> h = null)
		{
			PlayerATotal = a;
			PlayerBTotal = b;
			InvalidChoices = h ?? new HashSet<int>();
			PlayerAHasWinningStrategy = false;
		}

		public Scenario Clone()
		{
			return new Scenario(PlayerATotal, PlayerBTotal, InvalidChoices);
		}

		public void PlayerAChoose(int x)
		{
			PlayerATotal += x;
			InvalidChoices.Add(x);
		}

		public void PlayerBChoose(int x)
		{
			PlayerBTotal += x;
			InvalidChoices.Add(x);
		}

		public bool PlayerAHasWinningChoice()
		{
			return PlayerHasWinningChoice(PlayerATotal);
		}

		public bool PlayerBHasWinningChoice()
		{
			return PlayerHasWinningChoice(PlayerBTotal);
		}

		public bool IsInvalidChoice(int x)
		{
			return InvalidChoices.Contains(x);
		}

		public bool PlayerHasWinningChoice(int playerTotal)
		{
			for(int i = 0; i <= Scenario.maxChoice; i++)
			{
				if(!IsInvalidChoice(i) && (playerTotal + i >= Scenario.winTotal))
					return true;
			}

			return false;
		}
	}
}

Bool canwin(int n, int Max)
{
int m = n+1;
int rem = max%m;

if (rem == 0) {
// if m is odd and rem is 0, then we are loosing for sure..
if (m &1 )
return false;
// Rem is 0 but m is even, then we are winning.
return true;
}

if (rem <= (m+1)/2)
return true;

return false;
}

Bool canwin(int n, int Max)
{
	int m = n+1;
	int rem = max%m;

	if (rem == 0) {
		// if m is odd and rem is 0, then we are loosing for sure..
		if (m &1 )
			return false;
		// Rem is 0 but m is even, then we are winning.
		return true;
	}

           if (rem <= (m+1)/2)
		return true;

	return false;
}

Bool canwin(int n, int Max)
{
	int m = n+1;
	int rem = max%m;

	if (rem == 0) {
		// if m is odd and rem is 0, then we are loosing for sure..
		if (m &1 )
			return false;
		// Rem is 0 but m is even, then we are winning.
		return true;
	}

           if (rem <= (m+1)/2)
		return true;

	return false;
}

Boolean canIWin(int maxChoosableInteger, int desiredTotal) { 
    
   return canIWin(max, -1, desiredTOtal, true);

}


canIWin(max, chosen, desired, isPlayerOne){

    for(int j = 1 ; j <= max; j++)
        if (j != chosen && j>=desired)
            return isPlayerOne;
    
    boolean result = false;
    for(int i = 1; i <= max; i++)
        if (i != chosen && desired -i > 0)
            result = result || canIWin(max, i, desiredTOtal-i, !isPlayerOne);
        
    return result;
    
}

static boolean canIWin(int max, int total) {
		while (total > 0) {
		  	if (max <= 0) return false;
		  	total -=  max;
		  	max -= 2;
		}
		return true;
	}

while(number){
number = number % maxChoosableInteger;
if(number.ischoosable()){ // This has to remove the number once its got choosen
player.value =- number;
if(player.value<=0)
return player;
}
remove number;
}