# Challenge: Find the minimum amount of draws possible for a list of integers

• RaamGeneral
RaamGeneral
TL;DR Summary
given a list of integers, find the minimum value of a certain property given by pairing the elements
Hello. Sorry if the title is a bit vague.

I'm doing this challenge (google foobar) and even though it's not very elegant to ask for help, it's not like I'm going to win any kind of prize for it. In any case I'd like some suggestions since my current solution fails 2 tests on 5. The most probable reasons might be:
- the algorithm is not correct (maybe it doesn't correctly evaluate some cases)
- the algorithm is too slow, which I'm pretty sure it is.

Given any two integers ##a## and ##b##, suppose that ##a<b##, and consider the function ##f(a,b)=(2a, b-a)##. There are certain pairs such that repeated applications of ##f## produce a loop of results. I discovered that this does not happen when $$\frac{a}{a+b}=\frac{\mathrm{odd_number}}{2^k}$$ with ##a/(a+b)## reduced to their lowest terms: in this case I say that the pair (two elements) ends up in a draw.

The problem: you're given a list of non negative integers and must find the minimum amount of draws possible. I suppose that if the list contains an odd number of elements, one will never be paired and may be considered a draw too (one element).

For this problem I couldn't get a better algorithm than this one, although I tried a few other ways which made not much difference in run time (for certain cases).

Python:
def find_least_draws(seq):
n = len(seq)
if n <= 1:
return n

R = n
for i in range(1, n):
if seq[0] == seq[i]:
continue

# it returns 0 or 2
A = does_draw(seq[0], seq[i])
new_seq = [el for j, el in enumerate(seq) if j != 0 and j != i]
B = find_least_draws(new_seq)
C = A + B
if C == n % 2:
return C

if C < R:
R = C

return R

I tried to avoid creating new lists (new_seq) and other "traversal strategies", but actually I'm still not sure where (if) the trick is (maybe to decrease the amount of possible checks/computations to make). I kind of see that this problems may have something to do with graphs or trees, but I don't find it simple to visualize the correct structure. I also have found a "matrix" representation, but again I'm not sure how to best manipulate such matrix to achieve the result.

A small suggestion is welcome. Thank you.

$$f(a,\ b)=(2a,\ ba)$$
$$f^2(a,b):=f(f(a,\ b))=(4a,\ b-3a)$$
$$f^3(a,\ b)=(8a,\ b-7a)$$
$$f^n(a,\ b)=(2^na,\ b-(2^n-1)a)$$

Last edited:
RaamGeneral said:
- the algorithm is too slow, which I'm pretty sure it is.
I discovered that this does not happen when $$\frac{a}{a+b}=\frac{\mathrm{odd_number}}{2^k}$$ with ##a/(a+b)## reduced to their lowest terms: in this case I say that the pair (two elements) ends up in a draw.
We need some examples here. what happens if 2a becomes greater thant b-a, do you then exchange an and b? i don't see when a pair draws.

It does seem like the computation of does_draw() is the problem. You could use a table or the @cache function decorator to not compute this function over and over

Your recursion seem to use about n (n-2)(n-4) ..... 4. 2 steps for even n.

It can be made faster by only using the pairs that do draw in the recursion. We are only interested in finding pairs that draw.

You start the recursion by what you do now: finding a partner seq for seq[0], but now you only do the recursion if they do draw.
If seq[0] does not draw with anyone, you can just call find_least_draws() with a sequence without seq[0]
in it.

This should go much faster if there are more non draws than draws.

Another thing you could try is to check if the graph of the drawing numbers is connected, and if not, separate them, and compute the maximum number of draws for the different components separately.
It would be nice to have an example here too, of a list of numbers and the maximum amount of draws.

You're right about the function, I should show some examples or be more clear. In fact I was unprecise
f(a, b) = (2a, b-a) if a<b
(a-b, 2b) if b<a

Examples:
not does_draw:
0: (4, 6)
1: (8, 2)
2: (6, 4)
3: (2, 8)
4: (4, 6)

does_draw:
0: (3, 5)
1: (6, 2)
2: (4, 4)I'm pretty positive that the function does_draw is correct since it got extensive testing and theoretical-backed argument (I threw away the notes though, but they start as with @anuttarasammyak)As for @willem2 reply, I will have to read it carefully later.

RaamGeneral said:
f(a, b) = (2a, b-a) if a<b
(a-b, 2b) if b<a
if a=b, f(a,a)= ?

For the context of this problem f(x, x) is undefined, but does_draw still works as expected. In fact a pair may either produce a loop of results (never reaching any (x, x)) or end up in (x, x), which is what does_draw lets us know (it can do of course by generating and inspecting results of application of f, or by the odd_number/2^k rule).

Google use Foobar for sifting potential employees. This is not something that we should be doing here, and PF has no rights to publish the details of Foobar questions.

RaamGeneral said:
Examples:
not does_draw:
0: (4, 6)
1: (8, 2)
2: (6, 4)
3: (2, 8)
4: (4, 6)

does_draw:
0: (3, 5)
1: (6, 2)
2: (4, 4)
A preliminary observation
Odd numbers can appear in 0: only.
If Max(a,b)/Min(a,b)=2 then in next next step it loops back.
If Max(a,b)/Min(a,b)=3 then in next step it draws.

pbuk said:
Google use Foobar for sifting potential employees. This is not something that we should be doing here, and PF has no rights to publish the details of Foobar questions.
Thread closed temporarily for Moderation...

RaamGeneral said:
I'm doing this challenge (google foobar) and even though it's not very elegant to ask for help, it's not like I'm going to win any kind of prize for it.

After a Mentor discussion, the thread will remain closed.

## 1. How do you determine the minimum amount of draws for a list of integers?

To find the minimum amount of draws for a list of integers, you need to identify the frequency of each unique integer in the list. The minimum amount of draws will be equal to the total number of integers in the list minus the frequency of the most frequently occurring integer.

## 2. Can you provide an example to illustrate how to find the minimum amount of draws?

Sure! Let's say we have a list of integers: [1, 2, 2, 3, 3, 3]. The most frequently occurring integer is 3, which appears 3 times. Therefore, the minimum amount of draws for this list would be 6 (total number of integers) - 3 (frequency of most frequent integer) = 3.

## 3. What is the significance of finding the minimum amount of draws for a list of integers?

Finding the minimum amount of draws for a list of integers can help in identifying the maximum number of unique integers that can be drawn from the list without repeating any integer more times than necessary. This information can be useful in various applications, such as optimizing resources or minimizing redundancy.

## 4. Are there any special cases to consider when determining the minimum amount of draws?

Yes, one special case to consider is when all integers in the list are unique. In this scenario, the minimum amount of draws will be equal to the total number of integers in the list, as there are no repeated integers to draw more than necessary.

## 5. How can the concept of minimum amount of draws be applied in real-world scenarios?

The concept of minimum amount of draws can be applied in various real-world scenarios, such as inventory management, scheduling tasks, or organizing events. By determining the minimum number of resources needed to fulfill a certain requirement, organizations can optimize their operations and minimize waste.

• Programming and Computer Science
Replies
4
Views
1K
• Programming and Computer Science
Replies
17
Views
1K
• Programming and Computer Science
Replies
29
Views
2K
• Programming and Computer Science
Replies
34
Views
3K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
97
Views
7K
• Programming and Computer Science
Replies
12
Views
2K
• Programming and Computer Science
Replies
75
Views
5K
• Programming and Computer Science
Replies
2
Views
2K
• Programming and Computer Science
Replies
5
Views
1K