CareerCup

Min Coin Problem

dp[0] = 1;
 for (int i=0; i < N; i++)
    for(j = a[i]; j <= W; j++)
           dp[j] |= dp[j-a[i]];
 return dp[W];

public static boolean isScorePossible(int[] points, int value){
		int status [] =new int [value+1];
		status [0]=1;
		for (int i=0;i<points.length;++i){
			for (int j=points[i];j<=value;++j){
				status[j]+=status[j-points[i]];
			}
		}
		
		return status[value]>0;

}

bool isScorePossible(int[] points, int finalScore)
{
  Map<Integer,Integer> myMap = new HasMap<Integer, Integer>();
  
  for(int i=0;i<points.length();i++) {
     myMap.put(points[i],points[i]);
  }

for(int i=0;i<points.length(); i++) {

if(points[i]<=finalScore) {
  int hold = Math.abs(points[i] - finalScore);
  if(myMap.containsKey(hold)){
  return true;
  }
  else {
  while ((points[i] + points[i])<finalScore){
  int hold = (points[i] + points[i];
  if(myMap.containsKey(hold) || hold==finalScore){
  return true;
  } 
  }
}
}
else
return false;
}
}

bool subsetSum(vector<int> &candidates, int sum) {
    sort(candidates.begin(), candidates.end());
    vector<bool> dp(candidates.size()+1, false);
    
    dp[0] = true;
    
    for (int i = 1; i <= sum; ++i) {
        for (int j = 0; j < candidates.size(); ++j) {
            if (candidates[j] <= i) {
                dp[i] = dp[i] | dp[i-candidates[j]];
                if (dp[i]) break;
            } else {
                break;
            }
        }
    }
    
    return dp[sum];
};

/**
	 * N - array length
	 * M - value to check
	 * 
	 * time: O(N*M)
	 * space: O(lg M)
	 */
	boolean isScorePossible(int value, int[] arr){
		
		Arrays.sort(arr);
		
		BitSet sol = new BitSet(value+1);
		sol.set(0);
		
		for( int i = arr[0]; i < value+1; i++ ){
			
			for( int j = 0; j < arr.length; j++ ){
				if( arr[j] > i ){
					break;
				}
				
				if( sol.get(i-arr[j]) ){
					sol.set(i);
					break;
				}
			}			
		}
		
		return sol.get(value);
	}

boolean SubSetSum(int[] S, int target){
	// I assume that all the integers in S and the target is positive
	boolean[] A = new int[target];
	for(int i = 0; i<target; i++){
		int value = false;
		for(int j = 0; j<S.length; j++){
			if(S[j] == i+1){
				value = true;
				break;
			}
			else if(i+1 - S[j]> 0 && A[i+1-S[j]]){
				value = true;
				break;
			}
		}
		A[i] = value;
	}
	return A[target-1];
}

def isScorePossible(points, result):
if(result in points):
return True
if(result<0):
return False
else:
flag = False
for point in points:
if(isScorePossible(points, (result-point)) or flag):
return True
return False

Is this just a backtracing problem?

def is_score_possible(n, points):
    if n in points:
        return True
    sub_points = [point for point in points if point < n]
    for pt in sub_points:
        if is_score_possible(n-pt, sub_points):
            return True
    return False



points = [3, 7]
print is_score_possible(10, points)
print is_score_possible(9, points)
print is_score_possible(8, points)
print is_score_possible(11,points)

def gcd(lst):
"""
>>> gcd([14,24,6,8])
2
>>> gcd((6,8,9,12,14))
1
>>> gcd([6, 9, 18, 36])
3
"""
non_zeroes = []
for elem in lst:
if elem != 0:
non_zeroes.append(elem)
assert len(non_zeroes) >= 1, "Error! Must have at least 1 non-zero item in the list!"
if len(non_zeroes) == 1:
return non_zeroes[0]
m = min(non_zeroes)
m_index = non_zeroes.index(m)
for i in range(len(non_zeroes)):
if i != m_index:
non_zeroes[i] %= m
return gcd(non_zeroes)

def is_score_possible(pts, score):
"""
>>> is_score_possible((3, 7), 10)
True
>>> is_score_possible((3, 7), 9)
True
"""
return score % gcd(pts) == 0

def gcd(lst):
    """
    >>> gcd([14,24,6,8])
    2
    >>> gcd((6,8,9,12,14))
    1
    >>> gcd([6, 9, 18, 36])
    3
    """
    non_zeroes = []
    for elem in lst:
        if elem != 0:
            non_zeroes.append(elem)
    assert len(non_zeroes) >= 1, "Error! Must have at least 1 non-zero item in the list!"
    if len(non_zeroes) == 1:
        return non_zeroes[0]
    m = min(non_zeroes)
    m_index = non_zeroes.index(m)
    for i in range(len(non_zeroes)):
        if i != m_index:
            non_zeroes[i] %= m
    return gcd(non_zeroes)

def is_score_possible(pts, score):
    """
    >>> is_score_possible((3, 7), 10)
    True
    >>> is_score_possible((3, 7), 9)
    True
    """
    return score % gcd(pts) == 0

Mod the score by each point (sorted by descending value). If 0, then we constructed the score by some product of the points. Otherwise it's impossible.

def isScorePossible(points, score):
for point in sorted(points, reverse=True):
score %= point
return score == 0

Mod the score by each point (sorted by descending value). If 0, then we constructed the score by some product of the points. Otherwise it's impossible.

def isScorePossible(points, score):
    for point in sorted(points, reverse=True):
        score %= point
    return score == 0

int rem = score;
Arrays.sort(points);
Arrays.sort(points, Collections.reverseOrder());
for(int a : points) {
if(score % a == 0 || rem % a == 0) {
return true;
} else {
rem = rem % a;
}
}
return false;

def isScorePossible(points, value):
for i in points:
mod = value % i
if mod in points or mod == 0:
return True

def isScorePossible(points, value):
for i in points:
mod = value % i
if mod in points or mod == 0:
return True

def isScorePossible(points, value):
for i in points:
mod = value % i
if mod in points or mod == 0:
return True

def isScorePossible(points, value):
for i in points:
mod = value % i
if mod in points or mod == 0:
return True

def isScorePossible(points, value):
	for i in points:
		mod = value % i
		if mod in points or mod == 0:
			return True

static boolean recurse(int value){
		if (value == 0) return true;
		else if(value > 0)
			return (recurse(value-3) || recurse(value-7));
		else return false;
	}