Problem Statement: Refer Equal Average

Problem Analysis:

Given a sequence A1, A2, …, AN. Let, m=N%K; q= N//K i.e., N = q*K + m.

If following arrangement (refer table) exist, solution exist and answer “YES”, otherwise “NO”

row # | col 1 | col 2 | …… | col q | col (q+1) |
---|---|---|---|---|---|

1 | B1 | B1 | B1 | B1 | B1 |

2 | B2 | B2 | B2 | B2 | B2 |

. | . | . | . | . | . |

m | Bm | Bm | Bm | Bm | Bm |

m+1 | C1 | C1 | C1 | C1 | |

m+2 | C2 | C2 | C2 | C2 | |

. | |||||

k | Ck-m | Ck-m | Ck-m | Ck-m |

*The above table can be written as solution array [B1,B2,…,Bm,C1,C2,…Ck-m] - repeat “q” times followed by [B1,B2,…,Bm] once*

Each Bi (i ranges from 1 to m), has to have a frequency of (q+1). Each Cj (j ranges from 1 to (k-m)), has to have a frequency of (q)

- From given array A, make a frequency table. I used Counter in itertools to make the same
- Let’s say every distinct number Dp exist Fp number of times
- If distinct numbers (Dp) is more than k, i.e., p>k, we cannot form above table, so answer is “NO”
- For each Fp, find x1 x2 x3 such that Fp = x1 (q+1) + x2 (q+1)(q) + x3 (q). As multiple solution exists, we find x such that we have minimum x1and x3 and maximum x2
- Each Dp has to be placed in exactly x1 rows from 1 to m i.e., rows having B’s in table
- Each Dp has to be placed in exactly x3 rows from (m+1) to k i.e., rows having C’s in table
- Now we have additional flexibility to
- Either place x2 (q+1) rows of C’s (or)
- Either place x2 (q) rows of B’s (or)
- Subdivide x2 = x4 + x5 and keep x4 (q+1) C’s and x5 (q) B’s

- Using above point, we can solve the problem by filling missing rows of B’s and C’s

My solution: Refer the link. Hope this helps.