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.