CareerCup

27 27 (27)
9 9 (9)
3 3 (3)
1 1 (1)

[5 Tries]


1) split into three groups 27 each
2) weigh the two groups of 27 each.
3a) If both are equal the lighter ball is on the 3rd group of 27
3b) If they are unequal the lighter group on the balance should have the lighter ball
4)Pick up the suspected group , Split into two groups of 13 each and weigh them, so 13 13 1
5a) If they are equal the one extra ball is the lighter one
5b) If they are unequal pick the subgroup which contains the lighter ball
6) Split the subgroup of 13 into 6 6 1 and weight 6 and 6 against each other
7a) If they are equal the 1 extra ball is the lighter ball
7b) If they are unequal so we have the group of 6 which contains the lighter ball
8) Split the group of 6 into 3 3, one of that should be ligher pick the group of 3
9) Split the 3 into 1 1 1, weight 1 1 against each other.
10a) If both are equal the third ball is the lighter one.
10b) If they are unequal , the one which weights low is the lighter ball

Always work with thirds. Going off the previous answer where you now have a suspected group of size 27. Break this into three groups of 9.compare two groups. If same it's in the third, otherwise take the lighter group of 9. The lighter group of 9 is solved similarly again with thirds, comparing two groups of 3 and taken a culprit group of 3 containing lightest group. A group of three just needs a comparison of two items, again comparing two groups that are a third of the population. This answer takes at most 4 comparisons

public static int find_lighter(int a[],int start, int end){

	if(start == end) //exit condition
		return start;
   //divide this array into three.
   int parts = (end+1-start)/3;
   
   //store start and index of each part into temporary variable to avoid creation of new //arrays.
   int firstStart = start;
   int firstEnd = firstStart + parts-1;

   int secondStart = firstEnd +1;
   int secondEnd   = secondStart +parts -1;

   int thirdStart = secondEnd+1;
   int thirdEnd =  a.length-1;
   
   //calculate sum
   int sum1 = sum(a,firstStart,firstEnd);
   int sum2 = sum(a,secondStart,secondEnd);
   int sum3 = sum(a,thirdStart,thirdEnd);
   
   if(sum1 == sum2){
		//sum3 has the lighter
		return find_lighter(a,thirdStart,thirdEnd);
   }
   else if(sum1 > sum2){
		//sum2 has the lighter
		return find_lighter(a,secondStart,secondEnd);
   }else{
		//sum1 has the lighter
		return find_lighter(a,firstStart,firstEnd);
   }
}
   public static int sum(int a[],int start, int end){
		
		int sum = 0;
		for(int i=start;i<=end;i++){
			sum = sum + a[i];
		}
		return sum;
	}

What do you mean by using dynamic programming??

first knew 'dynamic programming' by this problem. I looked up in wiki and implemented. would you correct me if there is something weird?

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

static int s_weight_subtotal[3][81];

int get_weight(int weight[], int start, int len)
{
	int i;

	if(len==1)
		return weight[start];

	i = log(len)/log(3)-1;

	if(!s_weight_subtotal[i][start]) {
		s_weight_subtotal[i][start]	= get_weight(weight, start, len/3) + get_weight(weight, start+len/3, len/3) + get_weight(weight, start+(len*2/3), len/3);
	}
		
	return s_weight_subtotal[i][start];
}

int find(int weight[], int start, int len)
{
	if(len==1)
		return start;

	if(get_weight(weight, start, len/3) < get_weight(weight, start+len/3, len/3)) {
		return find(weight, start, len/3);
	}
	else if(get_weight(weight, start+len/3, len/3) < get_weight(weight, start+(len*2/3), len/3)) {
		return find(weight, start+len/3, len/3);
	}
	else {
		return find(weight, start+(len*2/3), len/3);
	}
}

void dump_weight_subtotal(void)
{
	int i, j;
	for(i=0; i<3; i++) {
		printf("[%d] ", i);
		for(j=0; j<81; j++) {
			if(s_weight_subtotal[i][j]!=0)
				printf("(%d: %d), ", j, s_weight_subtotal[i][j]);
		}
		printf("\n");
	}
}

int main(int argc, char* argv[])
{
	memset(s_weight_subtotal, 0x00, sizeof(s_weight_subtotal));

	int weight[81];
	for(int i=0; i<81; i++)
		weight[i] = 90;
	weight[50] = 12;

	int idx = find(weight, 0, 81);
	printf("lightest: idx=%d, value=%d\n", idx, weight[idx]);

	dump_weight_subtotal();

	return 0;
}

Python:
O(n) subproblems each taking O(1) time = O(n) time
O(n) space for the DP array

def findcompares(num):
	arr = [0 for x in range(num+1)]

	arr[0] = 0; arr[1] = 0; arr[2] =1; arr[3] = 1;

	for i in range(4,num+1):
		thevals = helper(i)
		arr[i] = max(arr[thevals[0]], arr[thevals[1]], arr[thevals[2]])+1

	return arr[num]

def helper(num):
	r = num%3
	d = num/3

	if r==0:
		return d,d,d
	if r==1:
		return d,d,d+1
	if r==2:
		return d,d+1,d+1

print findcompares(81)

use modified merge logic,during the joining only return array values with distinct values

You can change the BALL_MAX define for any divisible by 3. Try 81*81*81 for example.

time: O(log3(n)) best case, worst case is O(n)
space: O(n)

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

#define BALL_MAX (81)
#define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
#define BALL_OFFSET(_ball, _len, _off) (_ball + ((_len / 3) * (_off)))

static long iterations;

inline size_t min3(size_t a, size_t b, size_t c)
{
	return MIN(MIN(a, b), c);
}

size_t weight(size_t *ball, size_t len)
{
	size_t i;
	size_t ret = 0;
	for (i = 0; i < len; ++i)
		ret += *(ball + i);
	return ret;
}

bool find_lightest_ball(size_t *ball, size_t len, size_t *min_val /* OUT */)
{
	iterations++;
	if (len == 3) {
		*min_val = min3(*ball, *(ball + 1), *(ball + 2));
		return true;
	} else if (len == 9) {
		size_t w1, w2, w3;
		w1 = weight(BALL_OFFSET(ball, len, 0), len / 3);
		w2 = weight(BALL_OFFSET(ball, len, 1), len / 3);
		w3 = weight(BALL_OFFSET(ball, len, 2), len / 3);

		if (w1 == w2 && w2 == w3)
			return false;
		else if (w1 < w2)
			return find_lightest_ball(BALL_OFFSET(ball, len, 0), len / 3, min_val);
		else if (w2 < w1)
			return find_lightest_ball(BALL_OFFSET(ball, len, 1), len / 3, min_val);
		else
			return find_lightest_ball(BALL_OFFSET(ball, len, 2), len / 3, min_val);
	} else {
		return find_lightest_ball(BALL_OFFSET(ball, len, 0), len / 3, min_val) ||
			find_lightest_ball(BALL_OFFSET(ball, len, 1), len / 3, min_val) ||
			find_lightest_ball(BALL_OFFSET(ball, len, 2), len / 3, min_val);
	}
}

int main(int argc, char *argv[])
{
	size_t i, ball[BALL_MAX];
	size_t w, w2, l_i;
	size_t min_ball_val;

	srand(time(NULL));

	w = rand() % 100 + 1;
	for (i = 0; i < BALL_MAX; i++)
		ball[i] = w;

	l_i = rand() % BALL_MAX;
	while ((w2 = rand() % 100) >= w);

	ball[l_i] = w2;

	for (i = 0; i < BALL_MAX; i++)
		printf("ball #%u: %u\n", i+1, ball[i]);

	find_lightest_ball(ball, sizeof(ball) / sizeof(*ball), &min_ball_val);
	printf("lightes ball: %u\n", min_ball_val);
	printf("number of iterations: %ld\n", iterations);

	return 0;
}

#include <stdio.h>
#include <stdlib.h>
//(1. Num of left ball is odd )take out 1 ball each time randomly, ,if balance
//between 2 sides, randow ball is target; if not, find the smaller one
//group to recursive; (2.Num of left ball is even). Compare both size, using smaller one group
//to recursive.
int recursion_cal(int a[]);
int main()
{

int i=0;
int a[81];
for (i=0;i<81;i++)
a[i]=2;
a[48]=1;

return recursion_cal(a);


//return 0;
}
int recursion_cal(int a[])
{
int pos_rand_ball;
int size_a=sizeof(a)/4;//how many items in array A.

if (size_a%2==0)//even
{
int i=0;
int group_A[size_a/2];
int tot_group_A=0;
int group_B[size_a/2];
int tot_group_B=0;
for( ;i<size_a;i++)
{
tot_group_A=tot_group_A+a[i];
tot_group_B=tot_group_B+a[size_a/2+i];
group_A[i]=a[i];
group_B[i]=a[size_a/2+i];
}
recursion_cal(tot_group_A<tot_group_B?group_A:group_B) ;
}
else
{
int i=0;
int group_A[size_a/2];
int tot_group_A=0;
int group_B[size_a/2];
int tot_group_B=0;
pos_rand_ball=rand()%size_a;
int temp[size_a-1];
for(;i<pos_rand_ball;i++)
{
temp[i]=a[i];

}
for(;i<size_a-pos_rand_ball;i++)
temp[pos_rand_ball+i-1]=a[pos_rand_ball+i];
for(;i<sizeof(temp)/4;i++)
{
tot_group_A=tot_group_A+temp[i];
tot_group_B=tot_group_B+temp[sizeof(temp)/8+i];
group_A[i]=temp[i];
group_B[i]=temp[sizeof(temp)/8+i];
}
if (tot_group_A==tot_group_B)
{printf("the position of abnormal ball is %d",pos_rand_ball );
return pos_rand_ball;
}
else
recursion_cal(tot_group_A<tot_group_B?group_A:group_B) ;
}

}

I suppose you are given a balance too.
1) Divide into two groups 40-40
2) Take the lighter 40, divide into two groups 20-20 and measure
3) Take the lighter 20, divide into two groups 10-10 and measure
4) Take the lighter 10, divide into two groups 5-5 and measure
5) Take the lighter 5, measure any 4 such that 2-2 on each side of balance
6A) If balance is equal, the remaining ball is the lighter one.
6B) Else take the lighter 2, divide into two groups of 1-1 and measure.
7) You got the lighter one.