CareerCup

Google loves such probability computations based on dynamic programming

If P(n, x) is the probability that n die generate a sum greater than or equal to x, then P(n, x) follows this recursive definition:

P(n, x) = P(n-1, x) + (1/m) * sum { P(n-1, x-k), 1<=k<=m }

The first term computes the probability of generating a sum >=x using n-1 die, irrespective of the result of the nth dice. The second term computes the probability of generating a sum >=x-k using n-1 die and the probability of the nth dice generating a value k so that the total sum becomes >=x

Base cases:

P(1, x) = { 0 if x > m, (m-x+1) / m, otherwise }

clean code using recursion. Divide the output by the all combination to have the probability.
working for all the example cases mentioned in this thread.

static int findProbability (int n, int x, int m) {
		if (x <= 0) return pow(m,n);
		if (n == 0) return 0;
		int result = 0;
		int i;
		for (i = 1; i <= m; i++) {
			result += findProbability(n-1, x-i, m);
		}
		return result;
	}

So thinking about this issue, dont think this is meant to be a programming question. More of a analytical question on how you go about solving this.

The first thing to get started on this is to go by a example. Consider 2 dices with 6 sides. What are the possible sums we can get?
2, 3, 4 ... 12
Now what is the likelihood of 2? There is only one combination so: 1/36
For 3, we can have (1, 2) or (2, 1): so 2/36
For 4, we can have (1,3) or (3,1) or (2, 2): so 4/36 etc
You can see a pattern here: the middle numbers have a higher probability than the edge ones.

For 3 dices, the effect is even more:
3: 1/6^3
4: 3/6^3
5: 6/6^3 etc.

Basically this points to a pascal triangle, and for sufficiently large n this would be a normal distribution.

OK so now you have possibilities of the following sums in the generalized case.
n, n+1, n+2 ... mn

Lets call these sums as si
The probabilities of these numbers are pi, where pi derived from pascal triangle.

To find if a probability that sum would be greater than x:
for i=x..mn
sum(pi * si)

(would have been easier to represent if I had summation symbol.. not sure how to type it in this comment box.)

For sufficiently large n, this can be also found by doing an integral from x through mn on the normal distribution curve. Complexity of this would be O(1)!

Someway along this line:

number of different combinations to get a sum x:
f(m,x) = f(m,x - 1) + f(m - 1, x - 1)

probability = (f(m, x) + f(m, x - 1) + ... + f(m, m)) / (n ^ m)

store the intermediate information in a matrix M[i,j]=f(i,j)
complexity: O(m * x)

en.wikipedia.org/wiki/Binomial_theorem

mathworld.wolfram.com/Dice.html

I use recursive, and I think it's not good, I'm looking forward to seeing better solution


private static double equalGreater = 0;

public static void findProbability(int n, int m, int x, ArrayList<Integer> list, int index) {
if (index == n) {
if (sum(list) >= x) {
equalGreater++;
}
} else {
for (int i = 1; i <= m; i++) {
if (index == list.size()) { // first time
list.add(i);
} else { // the remaining steps just change it
list.set(index, i);
}
ArrayList<Integer> newList = (ArrayList<Integer>) list.clone();
findProbability(n,m,x,newList,index+1);
}
}
}

public static int sum(ArrayList<Integer> list) {
int r = 0;
for (int i = 0; i < list.size(); i++) {
r += list.get(i);
}
return r;
}

public static double getProbility(int n, int m, int x) {
int min = n;
int max = m*n;
if (x <= min) return 1;
if (x > max) return 0;
double doublen = n;
double doublem = m;
double total = Math.pow(doublem, doublen);
findProbability(n,m,x,new ArrayList<Integer>(), 0);
return equalGreater/total;
}

This can be solved using a recursive function. Since the sub-problems overlap with each-other, a dynamic programming approach speeds up the algorithm.
O(n*m)

#include<iostream>
#include<math.h>
using namespace std;

const long m=6;
const long n=12;
const long x=20;
int *table;


int func(int remainingX, int remainingDices ){


	int result =0;


	if(table[remainingX*n + remainingDices] != -1)
		return table[remainingX*n + remainingDices];


	if(remainingDices==1){
		if(remainingX >=1 && remainingX<=m)
			result =1;
		else
			result =0;
	}
	else{

		for(int i=1; i<=m; i++){
	
			if( (remainingX-i) >= (remainingDices-1) )
				result += func(remainingX-i, remainingDices-1);
		}
	}

	table[remainingX*n + remainingDices] = result;
	return result;

}


int main(int argc, char* argv[]){


	long tableSize = n*m*n + n +1;

	table = new int[tableSize];
	for(int i=0; i< tableSize; i++)
		table[i]=-1;

	double cumProb=0;
	for(int i=n; i<=x; i++){
		
		double tmpf = func(i,n);
		double probI = tmpf/(long)pow(m,n);
		cumProb += probI;
		

	}
	printf("prob for x => %ld is:%11.10f\n", x,  1-cumProb);

}

I mean 'sides' numbered from 1 to m not 'heads'

I tried like :-
1.) check if sum of any face with itself n number of times becomes greater than or equal to x.
2.) if it becomes exactly equals to x, then negative cases are (i^n - 1).
3.) if it becomes greater than x, then negative cases are (i-1)^n + if (combinations between (i-1) and i give sum less than x).

private static float findProbability(int n, int m, int x) {
		float prob = 0.0f;
		float totalCombinations = (float) Math.pow(m, n);
		System.out.println("total combs : " + totalCombinations);
		for (int i = 1; i <= m; i++) {
			if (i * n >= x) {
				int negativeCount = 0;
				if (i * n > x) {
					int count = 0;
					for (int j = 1; j < n; j++) {
						if (((i - j) * j + i * (n - j)) < x) {
							count++;
						}
					}
					negativeCount = (int) Math.pow(i - 1, n) + count;
				} else {
					negativeCount = (int) Math.pow(i, n) - 1;
				}
/* edit - start*/
int count1 = 0;
				for (int j=1; j<=m-i; j++) {
					for (int k=1; k<=i-2; k++) {
						if ((i+j) * j + k < x) {
							count1 ++;
						}
					}
				}
				
				negativeCount += count1 * n;
/* edit - end*/

				System.out.println("Negative Cases : " + (negativeCount));

				prob = (totalCombinations - negativeCount) / totalCombinations;
				break;
			}
		}

		return prob;
	}

Also, i think the first example in the question is wrong, total number of cases for n=4 and m=2 becomes 2^4 = 16 , not 8.

This is my solution ( O(n * n * m * m) ). There must be better solution than this.

public static double prob(int n, int m, int x) {
		int K = m * n + 1;
		int[] A = new int[K];
		int[] B = new int[K];
		for (int i = 1; i <= m; i++) {
			A[i] = 1;
		}
		for (int i = 1; i < n; i++) {
			for (int j = 1; j <= i * m; j++) {
				if (A[i] > 0) {
					for (int k = 1; k <= m; k++) {
						B[j + k] += A[j];
					}
				}
			}

			for (int j = 0; j < K; j++) {
				A[j] = 0;
			}

			int[] tmp = B;
			B = A;
			A = tmp;
		}

		int total = 0, upper = 0;
		for (int i = 0; i < K; i++) {
			total += A[i];
			if (i >= x)
				upper += A[i];
		}
		double prob = (double) upper / (double) total;
		return prob;
	}

number of positive integral solutions to the equation
X1 + X2 + X3 + ... + Xr = n (xi>=0) is (n+r-1)C (r).

in this question, no. of possibilities= no. of solutions to the equation:
X1 + X2 +... Xn + X(n+1)=x
/*X(n+1) as slack variable accounting for the >= sign*/

no of solutions = coefficient of X^x in the equation
[ (1+ X + X2 + X3 + ..... + X^m)^n ]*(1 + X + X2+......)
which should be reduced using Geometric Progression Formula.
total number of ways=m^n
Probability=no of solutions/total no. of ways.

#include <iostream>
#include "math.h"
using namespace std;

int sumLargerthan(int n,int m,int SUM, int sumNow)
{
if(n == 0 && sumNow >= SUM)
return 1;
else if(n == 0 && sumNow < SUM)
return 0;
else
{
int count = 0;
for(int i = 1;i<=m;i++)
{
//cout<<"i is "<<i;
int c = sumLargerthan(n-1,m,SUM,sumNow + i);
count = count + c;
//cout<<"count is "<<count<<endl;
}
return count;
}
}

void main()
{
int m = 6;
int n = 2;
int SUM = 3;
int sumNow = 0;
double largeCombin = sumLargerthan(n,m,SUM,sumNow);
cout<<"larger Combin is "<<largeCombin<<endl;
double totalCombin = pow(double(m),double(n));
cout<<"Total Combin is "<<totalCombin<<endl;
double prob = largeCombin/totalCombin;
cout<<"The prob is "<<prob<<endl;
}

(x+n)!/(c!*n!)

A theoretical probabilistic approach gives : P(sum > x) = 1 - x/(n*m)
Can anyone confirm this ?

For
n=4 m=2 x=8
ans: 1/16

Using forward dynamic (not backward, which complexity can be exponential), we have O( n*min(n*m,x)) algorithm:

calculate p(i, min(i*m,x)) for i = 1, 2, ... n following
p(n, x) = \sum_{i = 1}^m p(n-1, x-k) / m;
with boundary condition
p(1,k) == 1/m, k = 1,..m

The total possible number of sums is m^n (including duplicates)
A recursive method to get the number of the solution whose sum is larger or equal than x:

int get_larger_equal_x(int m, int n, int x)
{
   if (n==0 || x>m*n )
   {
       return 0;
   }
   else if(x<=n)
   {
      return m^n;
    }
    else
    {
        int sum=0;
        for (int i=1;i<m+1;i++)
        {
            sum+=get_larger_equal_x(n-1,m,x-i);
        }
        return sum;
     }
}

int le_sum=get_larger_equal_x(n,m,x);

The result probability = le_sum/(m^n)

package One;

public class Dice {
	static int num=0;
	static int count=0;
	public static void main(String[] args){
		int n=4;
		int m=2;
		int x=8;
		int den=(int)Math.pow(6,2);
		
		String s="";
		
		die(n,m,x,s);
		System.out.println(num);
		System.out.println(count);
	}
	
	public static void die(int n,int m,int x,String s)
	{
		if(x<n || x>(n*m))
		{
			s="No solution";
			System.out.println(s);
			return;
		}

		if(x==n)
		{
			for(int i=1;i<=n;i++)
			{
				s=s+i+"1 , ";
			}
			num++;
			System.out.println(s);
			return;
		}
		
		if(x==(n*m))
		{
			for(int i=1;i<=n;i++)
			{
				s=s+i+m+" , ";
			}
			System.out.println(s);
			return;
		}
		
		if(x>n)
		{
			x=x-n;
			for(int i=0;i<m;i++)
			{
				//if((m-i)<0)
				String ss=s+n+"*"+(i+1)+" , ";
				dice(n-1,m,x-i,ss);
			}
		}		
	}
	
	public static void dice(int n,int m,int x,String s)
	{
		count++;
		if(x<0)
		{
			return;
		}
		
		if(x>0 && n==0)
		{
			return;
		}
		
		if(x==0 && n==0)
		{
			num++;
			System.out.println(s);
			return;
		}
		
		if(n>0)
		{
			for(int i=0;i<m;i++)
			{
				//if((m-i)<0)
				String ss=s+n+"*"+(i+1)+" , ";
				dice(n-1,m,x-i,ss);
			}
		}
	}

}

O(m*n) space, O(m*n*n) time solution.
Optimized DP method.
Usage example: solve(6, 1, 3) will return 0.5 (because 4, 5, 6 is greater than 3 and 1, 2, 3, is not greater than 3)
Btw, this is solution is only to demonstrate the dp way of solving this problem. A simpler math way can solve this problem much more efficiently, with a risk of numeric overflow though.
double solve(int m, int n, int x) //m : range; n , dices, x threshold.
{
if (x > m*n || x < n)
return 0;
vector<vector<int>> dp(2, vector<int>(m * n + 1));
for (int i = 0; i <= m * n; ++i)
dp[0][i] = min(i, m);
for (int i = 1; i < n; ++i)
{
fill(&dp[i%2][0], &dp[i%2][i], 0);
for (int j = i; j <= m * n; ++j)
dp[i%2][j] = dp[i%2][j - 1] + dp[(i - 1)%2 ][j - 1] - dp[(i - 1)%2 ][j - 1 - min(j - 1 , m)];
}
return double(dp[(n - 1)%2][m*n] - dp[(n-1)%2][x]) / dp[(n - 1)%2][m*n];
}

So ALgeek, what's the solution to this problem ?
I am a fan of dices-involved games (I mean pen and paper rpg), and I like to know the correct answer ! :-)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int hits[10];
int NUM;
int SIDES;

int diceCombo(int diceNumber, int diceValue, int sum)
{
	int i;
	sum += diceValue;
	if(diceNumber >= NUM){
//		printf("diceNum %d dicevalue = %d sum = %d **\n", diceNumber, diceValue, sum);
//		printf("***************\n");
		hits[sum]++;
		return sum;
	}
//	printf("diceNum %d diceValue = %d sum = %d\n", diceNumber, diceValue, sum);
	for(i=1;i<=SIDES;i++){
		diceCombo(diceNumber+1, i,sum);
	}
	return 0;
}


int main(int argc, char *argv[])
{
	int i;
	int total=0;
	NUM = atoi(argv[1]);
	SIDES = atoi(argv[2]);
	for(i=0;i<=NUM*SIDES;i++){
		hits[i]=0;
	}
	diceCombo(0, 0, 0);
	for(i=0;i<=NUM*SIDES;i++){
		if(hits[i]){
			total += hits[i];
		}
	}
	printf("total %d\n", total);
	for(i=0;i<=NUM*SIDES;i++){
		if(hits[i]){
			double prob = (double)hits[i] / (double)total;
			printf("sum %10d hits %18d prob %2.20f\n", i, hits[i], prob);
		}
	}
	return 0;
}

package Geeks;

import java.util.Arrays;

public class diceGame {
	public static void main(String args[])
	{
		int m=4,n=2,x=8;
		
		int count1=0;
		int totalCount=0;
		int atmost=m*n;
		double probability;
		int[][] count=new int[atmost+1][m+1];
		for(int[] a: count)
			Arrays.fill(a,0);
			for(int i=1;i<=n;i++)
			{
				
				 count[i][1]=1;
			
			
		}
		
		//m dices with n faces
			for(int s=1;s<=atmost;s++)
			{
				for(int dice=1;dice<=m;dice++)
				{
					for(int j=1;j<=dice/2;j++)
					{
						for(int k=1;k<s;k++)
						{
							
							count[s][dice]+=count[k][j]*count[s-k][dice-j];
							
						}
						
						
					}
					
					
					
				}
				
				totalCount+=count[s][m];
				if(s>x)
				count1+=count[s][m];
				
			}
			
		
			
			
		probability=(double)count1/totalCount;
		System.out.println("\nWinning probability is= "+probability);
	}
	
	

}

I think random simulation is the right way to go since a dice :
step 1 : generate n truly random numbers between 1 and m . add them together and store their sum in an array of Sum[].
step 2 : repeat step 1 Z times. ( Z is size of array Sum[] )
step 3 : count all entries of Sum[] whose values are bigger than x. divide that
count by the number of trials ( Z ) gives you the probability.

ps : if you choose Z reasonably high, you should be in the same ball park as the person
who computes the actual probability for each trial. + you do less work . this is less than
12 lines of codes in one function. the other guy needs to compute nChooseK and stuff
in an interview, he will probably screw up or not finish while you have time to finish and
test your results.

I am a Loler. Clap Clap Clap