CareerCup

for(i=1;i<28;i++) a[i]=0;
for(i=1;i<1000;i++) a[(i%100)+((i/10)%10)+(i/100)]++;
result=0;
for(i=1;i<28;i++){ result += a[i]*a[i]; }

return result;

import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Lottery1 {
	static HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>(40);
	static double possibility = 0;

	public static void main(String[] args) {
		prepareMap();
		countPossibility();
		System.out.println("Possibility = " + possibility+"\n Means that each 20th combination wins.");
		TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>(sumMap);
		System.out.println("Sorted possibilities of each sum variant:\n" + tm);
	}

	static void countPossibility() {
		for (Entry<Integer, Integer> sumEntry : sumMap.entrySet()) {
			possibility += Math.pow((double) sumEntry.getValue() * 0.001, 2);
		}
	}

	static void prepareMap() {
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				for (int j2 = 0; j2 < 10; j2++) {
					int sum = i + j + j2;
					addToMap(sum);
				}
			}
		}
	}

	static void addToMap(int sum) {
		Integer i = sumMap.get(sum);
		if (i == null) {
			i = 0;
		}
		i++;
		sumMap.put(sum, i);
	}

}

Possibility = 0.05525200000000001
Means that each 20th combination wins.
Sorted possibilities of each sum variant:
{0=1, 1=3, 2=6, 3=10, 4=15, 5=21, 6=28, 7=36, 8=45, 9=55, 10=63, 11=69, 12=73, 13=75, 14=75, 15=73, 16=69, 17=63, 18=55, 19=45, 20=36, 21=28, 22=21, 23=15, 24=10, 25=6, 26=3, 27=1}

Sorted possibilities show that there is some sort of thing like pascal triangle can be applied to the task. The question can be solved in pure combinatorial analysis..

I know its the least efficient, but I told him to run the loop of all numbers between 0 and 999,999 and take the sums, and add 1 to a counter if the sums are equal.

you mean a 6 digit number and sum of first 3 digits == last 3 digits??

Quick question: When was your interview? Is this a question from the onsite interview?

okay finally understood where my pascal was behaving wrong. here's the code using pascal method verified against bruteforce method.
Output:
Final Probability using Pascal triangle method: 0.055252. . Number of iterations: 29
Final Probability using brute force method: 0.055252. . Number of iterations: 1000000

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
//!computes sum of digits of a three digit number
inline long sumofdigits(const long& val){
	return ((val/100) + ((val%100)/10)+val%10);
}
int main(){
	int sumOfDigits=0,numOfDigits = 3, maxOfDigit=9;
	double totalSum = 0,triVal=0,k=0,totalNumbersWithEqualSum = 0,numOfIters=0;
	long totalNumLotTickets = 1000000; //0 to 999999
	vector<long> thirdRowPascal(15,0);
	for(;k<15;++k,++numOfIters) //take 14 values of 3rd row of pascal triangle
		thirdRowPascal[k]=((k+1)*(k+2)/2); 
	for(;sumOfDigits<14;++sumOfDigits,++numOfIters){	
		if(sumOfDigits>9)	//if sum>9 then two digits cannot be zero at same time so 
			triVal = pow((double)(thirdRowPascal[sumOfDigits]-3*thirdRowPascal[sumOfDigits-10]),2);			
		else
			triVal = pow((double)thirdRowPascal[sumOfDigits],2);
		totalSum+=triVal;
	}cout<<"Final Probability using Pascal triangle method:"<<(totalSum*2)/totalNumLotTickets
		<<". Number of iterations: "<<numOfIters<<endl;
	//verification using brute force method
	vector<long> totalSums(28,0);long firstdig=0,lastdig=0;numOfIters=0;
	for(long ii=0;ii<totalNumLotTickets;++ii,++numOfIters){	
		firstdig = ii/1000;	lastdig = ii%1000;
		if(sumofdigits(firstdig)==sumofdigits(lastdig))
			++totalNumbersWithEqualSum;
	}cout<<"Final Probability using brute force method:"<<totalNumbersWithEqualSum/totalNumLotTickets
				<<". Number of iterations: "<<numOfIters<<endl;
}

Anyone going to explain what the code means?

Hi,
Search in wiki 'pascal triangle' that should explain how blueskin.neo's solutions works, but regarding code you should do it your self...

Hi Everyone,

I came up with the following solution to the above problem. The combinations form a very weird series. Below is the code for it. Let me know if this can be done in a more efficient time.

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

#define MAX_SUM 27
#define NDIGIT 3
#define C0 1

int main(){
    register int TOTAL = 0;
    int mid = MAX_SUM/2;
    int curr;
    int prev_val[2] = {C0, NDIGIT};
       
    for(int sum=2; sum<=mid; sum++){
            curr = (prev_val[1] - prev_val[0]) + 1 + prev_val[1];
            TOTAL += 2*(prev_val[0]*prev_val[0]);
            prev_val[0] = prev_val[1];
            prev_val[1] = curr;
    }
    
    TOTAL += 2*(prev_val[0]*prev_val[0]) + 2*(prev_val[1]*prev_val[1]);
    
    printf("Winning Tickets = %d\n", TOTAL);
    return 0;
}

catalan number or a modified pascal triangle. This question is a duplicate

This solution is excellent, how did you come up with it?

1. 3 digits sum minimum, MIN_SUM = 0 
2. 3 digits dum Maximum ,  MAX_SUM = 27
3. let us take an Array A[10] = {0,1,2,3,4,5,6,7,8,9}
4. for Each sum From MIN_SUM to MAX_SUM
      find all 3 -digit combinations  which gives above sum .

/* program to find no of lottery  tickets */

void Sum( int *A, int i, int digit, int  *count, int Psum, int sum )
{
	if( digit <= 0 || psum > sum || i >= 10 )
	{
		return;
	}
	else if (psum == sum )
	{
		*count += 1;
		return;
	}
	else
	{
		sum( A, i,   digit-1, count, sum, psum + A[i] ) ;
		sum( A, i+1, digit-1, count, sum, psum + A[i] ) ;
		sum( A, i,   digit,   count, sum, psum  ) ;
	}
}

     
int main()
{
	long int count=0;
	long int CumulativeSum = 0;
	int i = 0;

	for( i = 0; i<= 27 ; i++ )
	{
		count = 0;
		
		sum(A, 0, 3, &count, i, 0 );
		
		CumulativeSum += *count ;
	}
	
	printf(" Totla number of combinations = %l \n", CumulativeSum ); 
	return;
}

Incase , if you find any bug, please let me know.

Brute force may works.

int a[6],count=0;
for(int i=0;i<=999999;i++)
{  
  for(int j=0;j<6;j++)
  {
    a[j]=i%(10^(j+1));
    i /= 10;
  }
  if((a[1]+a[2]+a[3])==(a[4]+a[5]+a[6]))
    count++;

}

@Roshan ... Great Solution Buddy

01718881819

55252

Draw a distribution of sums in the range [0,27] for any three digit number, and you'll figure that the number of cases that adds up to i are (i+1)*(i+2)/2. We have 1000 cases per side, which means 1M total cases: squaring every number of cases that adds to a certain sum will provide the result.

public static int cases() {
		int total = 0;
		for (int i=0; i<14; i++)
			total += (int) Math.pow(i*(i+1)/2, 2);
		return total*2;
	}

public void LotteryTest()
        {
            var values = new Dictionary<int, int>();
            for (int i = 0; i < 1000; i++)
            {
                string valueString = i.ToString().PadLeft(3, '0');
                var value = Convert.ToByte(valueString[0].ToString()) + Convert.ToByte(valueString[1].ToString()) + Convert.ToByte(valueString[2].ToString());
                if (!values.ContainsKey(value))
                {
                    values.Add(value, 1);
                }
                else
                {
                    values[value]++;
                }
            }
            var total = values.Sum(v => v.Value * v.Value); //combination of left 3 and right 3
        }

n = 9 * (enter the number of digits);
int b[n] = { 2,3,4,6,7,8,9,...n};
int a[n];
a[0] = 1;
for(int i =1;i<=n;i++)
{  
a[i] = a[i-1] + b[i-1];
}
for(i = 0;i<n;i++)
{
int result  += a[i] * a[i];
}
return (result);

Its a combinatorial problem:
break into 2 parts :
first and last 3 digit
1 digit - 10 possible values
2 digits - 100 possible values
3 digits - 1,000 possible values

so 10^n ,n = digit
3 digit = 1,000
we compare it against the same values which would be 1,000