Facebook Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Unfortunately it's not that simple. Let's say you have 8 of a certain element after modulo, and n/k is 2 and n%k is nonzero. It could be that there are 4 of these elements in each chunk of size k, or it could be that there are 3 and the first n%k elements contain the remaining 2. There thus become lots of different possibilities and combinations of possibilities, so it's not as simple as you would have it.
I don't think you really understand the analysis. It can prove that ai and ai+k is in the same set, and thus the numbers are naturally grouped by remainders. No necessary to consider the details of numbers, cause there are only k types. Not hard to find that if true for the original problem, the sum of remainder is divisible by k, and vice versa...
I came up with something that sounded quite similar and dismissed it because it didn't work, but maybe your solution is different. Can you clarify point 2 in your answer? What precisely do you mean by "The sum of k groups' remainder divisible by NUM"?
Let me give you what I think is a counterexample to what you're proposing, and let you clarify why it's not if it is indeed not a counterexample. Suppose you have an array that is size 30 and consists of all 1s, and that further k=9 and num=3. So it is 1, 1, 1, ..., 1, 1. Your analysis seems to claim that there will be "b groups of a + 1 numbers and k-b groups of a numbers", where b = n%k = 30%9 = 3 and a = 30/9 = 3. So I expect to see 3 groups of 4 numbers and 6 groups of 3 numbers. However, this is blatantly false for a case like this, because there's only one group of numbers after modulo.
It looks to me that you didn't consider that multiple groups may all contribute to the same remainder. Like here, all your 3 groups of 4 and 6 groups of 3 are contributing to a single remainder, 1. So then you have to ask the question as to how, given just a count of remainders, you'd see if they can be partitioned into these groups.
So you only get half the idea, in your case: you have 30 1's.
and there are total 9 groups, even all groups have the same number, we treat them as different groups (group 1 to 9), and we would arrange them like this: (the number is the group index)
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3
and each consecutive k elements contains exactly one element from each group, thus we only need to check the sum of the remainder of the 9 groups, in your case: all 1's, so sum is 1*9 = 9 = 0 mod 3. so ans is true;
Hope it help your understand
Alright, I think I understand what your idea is now. I'm still skeptical, however, because I don't think you have an algorithm for efficiently partitioning the elements into these groups that you propose.
This idea seems still similar to what I was thinking about before, though framed a little differently, and I ran into the same problem. The question is this: how will you efficiently determine which numbers to put into which groups? Like for example, let's say you have 6 numbers that are 2 mod NUM. Let's say n=50 and k = 20. So we know that we will have 20 groups, of which 10 will be of size 3, and 10 will be of size 2. Now your 6 numbers that are 2 mod NUM -- how will you determine whether these are 2 groups of 3, or
3 groups of 2? That makes a difference on your final answer! You could try both possibilities, but that has to be tried in combination, or so it seems, with all other choices of this nature!
Maybe I either 1) still don't understand your approach; or 2) maybe you have some efficient way of dealing with this sort of issue?
@eugene.yarovoi. The algorithm to partition numbers is easy, I didn't put it out because it's too obvious, which only needs a linear scan and a hash map or some thing else.
Assume you have k1 groups need p+1 numbers, and k2 groups need p numbers. You scan from left to right, and fill the group according to the remainder. If a group group is full, move to the next one.
Take your 30 1's example, all remainder are 1.
By simple calculation we know there are 3 group have 4 number and 6 group have 3.
Scan from left to right,
1-> remainder 1, put in group 1 which has remainder 1 (size 1)
1->remainder 1, put in group 1 (size 2)
1->remainder 1, put in group 1 (size 3)
1->remainder 1, put in group 1 (size 4)
1->remainder 1, since group 1 is full, put it in a new group: group 2
....
All you need to do is to keep a hash map, fill the group if it's not full, remove it from the hash map if it's full...
I think you don't really understand how the analysis really works, since it's actually building a mapping between the two problems...
Implementation should be the minor and easiest thing once your understand it.
You seem to be ignoring the fundamental point I'm trying to drive home. Answer me this from my post before:
Let's say you have 6 numbers that are 2 mod NUM. Let's say n=50 and k = 20. So we know that we will have 20 groups, of which 10 will be of size 3, and 10 will be of size 2. Now your 6 numbers that are 2 mod NUM -- how will you determine whether these are 2 groups of 3, or 3 groups of 2?
In other words, how will you make the decision as to which numbers to put in the larger groups and which to put in the smaller groups? It does make a difference in your final answer.
If you still don't see my point, then I propose this: according to you, the algorithm you're proposing is very simple. Any chance I could get you to write the code, or even write the code myself and ask you to review it and say whether you agree that it's what you had in mind? I'd love to test this approach against some test cases.
Maybe it's correct, maybe it'll turn out that somehow whenever there's any satisfying arrangement into groups, a greedy arrangement satisifies the conditions too, but I don't see a clear reason why this would be true.
I've just realized that the issue I mention can be solved via dynamic programming in something like O(NUM*k*n) time (maybe better with some optimizations), but you seem to think this issue doesn't need to be addressed at all.
As I said, it doesn't matter how the number arranged.
Take your example,
we know there are 10 2's and 10 3's:
we start to scan from left to right, fill the all groups to 2 instead of 3 (the 30 1's example is a typo, i meant to stop at size == 3 since I thought max size is 5)
so by the time you have scanned the 40th number, you should be able to get 20 groups, each group have size 2, some groups may have the same remainder, but that's not what we should concern. (If you have more than 10 groups, return false, which you can prove by lemma 1)
Then, you can scan from 41th to 50th, you should be able to put them in 10 different groups, other wise, return false (by lemma 1).
after all these, check the sum of the 20 groups.
We don't really care about the details of you 2 groups of 3, or 3 groups 2, since maybe both them work, or neither of them work.
Hope you get the idea this time.
@eugene.yarovoi
No. you could do much better than that. Use a hash table, only need linear time.
Even use a stl map, it took worst nlgn time.
Read the analysis plz, you seem don't quite get the idea
Another typo.. sry
As I said, it doesn't matter how the number arranged.
Take your example,
we know there are 10 2's and 10 3's:
we start to scan from left to right, fill the all groups to 2 instead of 3 (the 30 1's example is a typo, i meant to stop at size == 3 since I thought max size is 5)
so by the time you have scanned the 40th number, you should be able to get 20 groups, each group have size 2, some groups may have the same remainder, but that's not what we should concern. (If you have more than 20 groups, return false, which you can prove by lemma 1)
Then, you can scan from 41th to 50th, you should be able to put them in 10 different groups, other wise, return false (by lemma 1).
after all these, check the sum of the 20 groups.
We don't really care about the details of you 2 groups of 3, or 3 groups 2, since maybe both them work, or neither of them work.
Hope you get the idea this time.
"We don't really care about the details of you 2 groups of 3, or 3 groups 2, since maybe both them work, or neither of them work."
I'd like to give you a direct counterexample to this.
Consider N= 8, K = 5, NUM = 11, and the input, after modulo by NUM, is { 1, 1, 1, 1, 4, 4, 4, 4}. So here we will have 5 groups, 8%5 = 3 of which will be size 2, and 5 - 8%5 = 2 of which will be size 1. Now, it's time to partition the input into groups. You seem to be saying that it doesn't matter whether I start placing 1s into groups of 1, or groups of 2, as it will be the same either way. I follow this advice and choose {1, 1}, {1, 1}. I now have one group of 2 and 2 groups of 1 left, so my remaining groups are {4, 4}, {4}, and {4}. I now compute 1 + 1 + 4 + 4 + 4, and it is 14. I check 14%11 == 0 -- it's false, so I return false.
Indeed, as you said, the array of size 8 is like this in terms of groups, where the number is the group index:
1 2 3 4 5 1 2 3
I had: group 1: {1, 1}
group 2: {1, 1}
group 3: {4, 4}
group 4: {4}
group5: {4}
So filling this in with the numbers from the group, I see that the groups I chose correspond to the arranged array 1 1 4 4 4 1 1 4. And true, consecutive arrays of size k=5 in this array are not divisible by NUM=11.
However, the answer of false is wrong. If I had arranged my groups containing 1s differently (by choosing 3 groups to place 1s in, namely {1, 1}, {1}, and {1}), my only choice to place the 4s would be {4, 4}, {4, 4}. I would then compute 1 + 1 + 1 + 4 + 4, which is divisible by 11! And lo' and behold the corresponding arrangement is 4 4 1 1 1 4 4 1, every subarray of size 5 of which is divisible by 11!
So here our groups were:
group 1: {4, 4}
group 2: {4, 4}
group 3: {1, 1}
group 4: {1}
group 5: {1}
As you can see, how elements are distributed within groups makes a difference in the answer.
My question now is: on what basis would your program have made the right choice between these two alternatives? It is not, as you say, that both of them are working or neither of them are working.
And though this is a very simple example because there's only 2 options here, I can show much more complex cases, which will have entire combinations of decisions to be made about how to distribute elements between groups.
I have good hopes that now that I've given such a specific example, one of two things can happen. Either:
1) If you are in fact mistaken, you can see the flaw in your approach;
or
2) If I still misunderstand, you will be able to pinpoint the exact way in which I misunderstand and say the right thing to make me understand.
@eugene.yarovoi
Yes, you are right about this. that's a nice counter example showing number arrangement actually matters. lemma 2 is not strong enough. Thank you!
The only algorithm I can come up is to use dp: The coin change problem with constrains on group of coins used...
That's all I can think of too. We have to use DP here, and the running time will be reasonable if NUM is small. We should be able to get something like O(NUM*k*n), which is bounded by O(NUM*n^2). So if NUM is small, we have a solution that is possibly very reasonable. If k and NUM are both small constants, then we even have a linear-time algo.
array = {80,17,90,82,27,19}, k=3, NUM=63
1. after modulus all array elements with NUM
array = {17,17,27,19,27,19}, exclude all zeros if there
2. hash all data and keep the count of each element
3. there should be K unique elements
4. sum of all unique elements should be equal to NUM
5. difference between the counts of any two elements should be at most differ by 1.
17 19 27 17 is Correct
17 19 27 17 19 is Correct
17 19 27 17 17 is not NOT Correct as 17 are 3 but 19's 27's are 1
proof: lets 17+19+27 is equal to 63 with K elements
next 19+27+x=63, so x should be 17
next 27+17+x=63, here again x should be 19
so the series would be like 17 19 27 17 19 27 (as per original array)
here series should start with element with max count and then next max count etc...
if the count of all elements are same then the order can be anything.
17 19 27 17 19 27
19 17 27 19 17 27 both are correct
if number of unique elements are less than K then
ex:
arr={2 ,5, 0 ,9 ,1, 9 ,9 ,4}
k=3, NUM=2,
hash array={0,1,0,1,1,1,1,0}
0's - 3
1's - 5
actually expected number of unique elements are 3(K), but here only 2 are there, so there is one number duplicate(K-2 = 1)
this duplicate should be 1, so for every set there should be 110...
here number of zeros are more than number of 1's (11, 11, 1)
so, series should start with element which is max occurrences
if number of 1 are 6 then 11 11 11 0 0 0, here number sets of 1's and 0's are same, in this case it works either order
very very appreciative solution...
I would like to know from u that how you select first three elements as 17,19,27.can u please & please explain an algorithm to select first sequence of k elements. like 17,19,27
And also it is not necessary to having k unique elements such as if we have
k=3,NUM=4,N=6
arr={6,1,1,9,2,5}
then hash{2,1,1,1,2,1} there are 2 unique numbers and sulution exists as Ans={1,1,2,5,9,5,6}.
Can you improve it
I have problem here
arr={2 ,5, 0 ,9 ,1, 9 ,9 ,4}
n=8,k=3, NUM=2,
hash array={0,1,0,1,1,1,1,0}
so if i start from {9,4,9.......} then i got{9,4,9,1,0,9,5,2}
and if start as {4,9,9....} then got {4,9,9,0,9,5,2,1}
these working but if start as {9,9,4.....}then getting no working solution...................Can u explain in this scenario how to???
here k=3, num=2
0's - 3
1's - 5
actually expected number of unique elements are 3(K), but here only 2 are there, so there is one number duplicate(K-2 = 1)
this duplicate should be 1, so for every set there should be 110...
here number of zeros are more than number of 1's (11, 11, 1)
so, series should start with element which is max occurrences
if number of 1 are 6 then 11 11 11 0 0 0, here number sets of 1's and 0's are same, in this case it works either order
I am agree with euqene.yarovi
actually it should be if distinct set of (arr[i]%NUM) >k
then print "-1"
else apply "YOUR ALGO"
I am sure.
@ eugene and dilip: You are correct, but it doesn't mean algo is completely wrong. It just needs some modifications. The basic idea is the same though.
Use following example to illustrate the basic concept:
Let say currently there is an array a[0 to k-1] with k elements and
(a[0]+a[1]+a[2]+...+a[k-1]) % NUM = 0
Then we append a new element to the end, ie. at a[k]. To still satisfy the condition that sum of consecutive k elements is divisible by NUM, we need
(a[1]+a[2]+...+a[k-1]+a[k]) % NUM =0
From both equations, we get (a[k]-a[0]) % NUM=0 or (a[k]%NUM) = (a[0]%NUM).
In other words, a[0] and a[k] has same reminder (after mod NUM) and let's call them reminder group 1.
Follow the same rule, (a[1]%NUM)=(a[k+1]%NUM) and let's call them reminder group 2. And (a[2]%NUM)=(a[k+2]%NUM), (a[3]%NUM)=(a[k+3]%NUM), and so on. In the end, there are k reminder groups.
This is why algo said there are k unique elements after modulus. However, among these k reminder groups, some of them can have same reminder(s). Therefore, the original statements by aglo needs a small modification to something like
"after modulus, the count of each reminders is N/K, N/K+1, multiple of N/K, or multiple of (N/K + 1)"
or
"after modulus, the count of each reminders is mN/k or m(N/k+1) where 1<=m<=k"
small correctness, it should be
"after modulus, the count of each reminders is mN/k+p where 1<=m<=k and 0<=p<min(k,N/k)".
I don't think we should be ignoring the '0' elements altogether. If N = 3, the total we are looking for is 63 and the input is (62, 1, 63, 4), then we should be returning [62, 1, 63] as the answer. If we ignore '0' elements altogether, we would end up returning -1.
Also, I think the problem can be treated as k-sum problem?
@buffalo: Consider the input 1 1 1 1 1... 1 1 (all ones for n=150 elements let's say), k=5 and and Num=100. The answer is no, but you would conclude the answer's yes simply because 150 1s can be partitioned evenly into 150/5 sections. There are other flaws too. I think this approach needs major revisions to work and is fundamentally broken as it stands.
int build_good_array(int *a, int n, int num, int k)
{
int i;
int ret = -1;
int *next = (int *)malloc(sizeof(int) * n);
int *result = (int *)malloc(sizeof(int) * n);
int *counts = (int *)malloc(sizeof(int) * num);
int *modulo_last = (int *)malloc(sizeof(int) * num);
memset(counts, 0, sizeof(int) * num);
memset(modulo_last, -1, sizeof(int) * num);
for (i = 0; i < n; ++i) {
next[i] = modulo_last[a[i] % num];
modulo_last[a[i] % num] = i;
++counts[a[i] % num];
}
int even_entries_count = 0;
int even_sum = 0;
int odd_sum = 0;
int odd_entries_count = 0;
int result_index = 0;
for (i = 0; i < num; ++i) {
if (counts[i] == (n / k)) {
++even_entries_count;
even_sum += i;
} else if (counts[i] == (n / k) + 1) {
odd_sum += i;
result[result_index++] = a[modulo_last[i]];
modulo_last[i] = next[modulo_last[i]];
++odd_entries_count;
} else if (counts[i] != 0) {
goto out; //out of luck.
// btw. a * (n/k) + b (n/k + 1) is also valid.
}
}
if (odd_entries_count != (n%k)) {
goto out;
}
if (even_entries_count != (k - (n%k))) {
goto out;
}
if ((even_sum + odd_sum) % num != 0) {
goto out;
}
// We have filled n%k entries already.
for (i = 0; i < num; ++i) {
if (counts[i] == (n / k)) {
result[result_index++] = a[modulo_last[i]];
modulo_last[i] = next[modulo_last[i]];
}
}
// Now we have k-length sequence sum divisible by NUM.
for (;result_index < n; result_index) {
i = result[result_index - k] % num;
result[result_index++] = a[modulo_last[i]];
modulo_last[i] = next[modulo_last[i]];
}
memcpy(a, result, sizeof(int) *n);
ret = 0;
out:
free(next);
free(result);
free(counts);
free(modulo_last);
return ret;
}
The following code needs some modification since count can be multiple of (n/k) or multiple of (n/k+1). Please see my reply above.
if (counts[i] == (n / k)) {
...
} else if (counts[i] == (n / k) + 1) {
......
}
This problem can be solved based on this simple property
For 'k' numbers to add up such that (a1+a2+...+ak) % NUM = 0, means the sum of the individual numbers a1, a2...ak remainder with NUM, must be equal to NUM. (So that total remainder becomes 0)
Further, since it requires that they be in order and sequential, that is after first k numbers, when you remove a1, and include ak+1, this new set must also have the same property. This implies that the mod value of every element removed must be matched by the next element.
Based on these observances, the algo is pretty simple
Create 'Num' Buckets, For every element calculate its mod with Num, and add to buckets. If the number of filled buckets are not equal to k, return not possible. If the total number of elements in each of the 'k' buckets are not equal, return not possible. If the sum of the bucket values(Mod values) is not equal to 'k', not possible.
The answer is then just to pick one number from each bucket in a round robin fashion.
------------------------
I think this is the simplest way to go about it
Edit: TYPE, the last condition is actually :If the sum of the bucket values(Mod values) is not equal to 'NUM', not possible:
No, it's really not that simple. A couple things:
1. There's no need for there to be k different buckets. Suppose the array is all 1s and k=5 and NUM = 5. Then any arrangement satisfies the conditions, even though there's only one bucket.
2. The sum of (a1 % NUM) + (a2 % NUM) +... + (ak % NUM) needs not add up to NUM. It can also add up to a multiple of NUM.
3. If you were to have k buckets, it could not be that the number of elements in each bucket is the same, since N is not necessarily divisible by k.
I recommend reading the discussion at the top of the page. It might shed some light as to why simple round-robin-like approaches to this problem fail.
so basically, we have at most k distinct number(after mod). then we use DP or whatever to check whether we can get the sum with k numbers(must include all distinct number and may possibly include some repeated number, can be done in DP when k is very large!) if not obviously false. else we can check every possibility. say 1,2,3 and two 4s, can be an example of k=5 number=14. so we check the count of these numbers(1,2,3,4). it should be N/k 1s, N/k 2s, N/k 3s, 2N/k 4s and possibly any combination of N%k elements from (1,2,3,4,4).
Let me know whether I get it!
I'm not sure I'm 100% clear on what you're saying, but that sounds about right. Trying every combination is probably a bad idea. Use dynamic programming.
I'm not saying we need try every combination. instead, we just count the remaining after decreasing by N/k, and check whether it's a possible combination of the sum set(1,2,3,4,4).
actually we don't need check the remaining. we just need check whether all number has count more than N/K*(the corresponding count in that sum set)
sorry for my bad explaination, I'm really not good at it. but I think the idea is simple and clear.
let me try an example
say k=6, number=14, N=20
the array after mod is {seven 1s, three 2s, six 3s, four 4s}
let's check whether it's possible.
1. use DP to find a sum set consisted of 6 numbers(must include all distinct numbers 1,2,3,4 and two other numbers) which sums up to 14
it can only be (1,2,2,2,3,4) or (1,1,2,3,3,4)
2. check (1,2,2,2,3,4)
so set is one 1, three 2s, one 3 and one four
N/k=3;
so
total count of 1s should be >= 3*one=3 and <3*one+k=9 true 3<=7<9
total count of 2s should be >= 3*three=9 and <3*three+k=15 false 3<9
...
so it's false;
3. check (1,1,2,3,3,4)
so set is two 1s, one 2s, two 3s and one four
N/k=3;
total count of 1s should be >= 3*two=6 and <3*two+k=12 true 6<=7<12
total count of 2s should be >= 3*one=3 and <3*one+k=9 true 3<=3<9
total count of 3s should be >= 3*two=6 and <3*two+k=12 true 6<=6<12
total count of 4s should be >= 3*one=3 and <3*one+k=9 true 3<=4<9
so it's true
if every set checks to be false, return false
static void printGroupedNumbers(int n, int k, int nUM, int[] list) {
HashMap<Integer, List<Integer>> modMap = new HashMap<Integer, List<Integer>>();
int sum = 0;
for (int index = 0; index < list.length; index++){
sum += list[index];
int key = list[index] % nUM;
List<Integer> keyVals = modMap.get(key);
if (keyVals == null)
keyVals = new ArrayList<Integer>();
keyVals.add(list[index]);
modMap.put(key, keyVals);
}
if (n%k != 0 || sum % nUM != 0 || modMap.keySet().size() != k) {
System.out.println("-1");
return;
}
int prev = -1;
for (int keyV : modMap.keySet()){
if (prev != -1){
if (prev != modMap.get(keyV).size())
{
System.out.println("-1");
return;
}
}
prev = modMap.get(keyV).size();
}
for (int itr = 0; itr < prev; itr++){
for (int keyV : modMap.keySet()){
System.out.print(modMap.get(keyV).get(itr) + " ");
}
}
}
static class Solution{
public static void main(String[] args){
int[] array1 = {80,17,90,82};
if(Rearrange(array1, 3, 63)==-1)
System.out.println(-1);
System.out.println();
int[] array2 = {2 ,5, 0 ,9 ,1, 9 ,9 ,4};
if(Rearrange(array2, 3, 2)==-1)
System.out.println(-1);
System.out.println();
int[] array3 ={22,23,44,2,1,65,86,107,128,149,170};
if(Rearrange(array3, 4, 21)==-1)
System.out.println(-1);
}
public static int Rearrange(int[] array, int k, int num){
int n = array.length;
HashMap<Integer, Integer[]> modHash = new HashMap<>();
for(int i=0;i<array.length;i++){
if(modHash.get(array[i]%num) == null){
Integer[] indeces = {i};
modHash.put(array[i]%num, indeces);
}
else{
Integer[] indeces = new Integer[modHash.get(array[i]%num).length+1];
for(int j=0;j<modHash.get(array[i]%num).length;j++)
indeces[j]=modHash.get(array[i]%num)[j];
indeces[modHash.get(array[i]%num).length]=i;
modHash.put(array[i]%num, indeces);
}
}
if(modHash.keySet().size()>k)
return -1;
if(n%k==0){
for(int i: modHash.keySet()){
if(modHash.get(i).length != n/k)
return -1;
}
for(int b=0;b<n/k;b++)
for(int i:modHash.keySet())
System.out.print(array[modHash.get(i)[b]]+" ");
}
else{
HashMap<Integer, Integer[]> modHashFirst = new HashMap<>();
HashMap<Integer, Integer[]> modHashSecond = new HashMap<>();
int bnum = (int)Math.ceil((double)n/(double)k);
for(int i: modHash.keySet()){
if(modHash.get(i).length%bnum != 0 &&
modHash.get(i).length%bnum != Math.floor((double)n/(double)k))
return -1;
if(modHash.get(i).length%bnum == 0)
modHashFirst.put(i, modHash.get(i));
else
modHashSecond.put(i, modHash.get(i));
}
//Full Buckets:
for(int b=0;b<n/k;b++){
for(int i:modHashFirst.keySet()){
int numOfFirstInFullBucket = (int)Math.floor((double)modHashFirst.get(i).length/(double)bnum);
for(int nb=0;nb<numOfFirstInFullBucket;nb++)
if(b*numOfFirstInFullBucket+nb<modHashFirst.get(i).length)
System.out.print(array[modHashFirst.get(i)[b*numOfFirstInFullBucket+nb]]+" ");
}
for(int i:modHashSecond.keySet()){
int numOfSecondInFullBucket = (int)Math.ceil((double)modHashSecond.get(i).length/(double)bnum);
for(int nb=0;nb<numOfSecondInFullBucket;nb++)
if(b*numOfSecondInFullBucket+nb<modHashSecond.get(i).length)
System.out.print(array[modHashSecond.get(i)[b*numOfSecondInFullBucket+nb]]+" ");
}
}
//Last Bucket (not full):
for(int i:modHashFirst.keySet()){
int numOfFirstInFullBucket = (int)Math.floor((double)modHashFirst.get(i).length/(double)bnum);
int numOfFirstInLastBucket = modHashFirst.get(i).length - numOfFirstInFullBucket*(n/k);
for(int nb=0;nb<numOfFirstInLastBucket;nb++)
System.out.print(array[modHashFirst.get(i)[numOfFirstInFullBucket*(n/k)+nb]]+" ");
}
for(int i:modHashSecond.keySet()){
int numOfSecondInFullBucket = (int)Math.ceil((double)modHashSecond.get(i).length/(double)bnum);
int numOfSecondInLastBucket = modHashSecond.get(i).length - numOfSecondInFullBucket*(n/k);
for(int nb=0;nb<numOfSecondInLastBucket;nb++)
System.out.print(array[modHashSecond.get(i)[numOfSecondInFullBucket*(n/k)+nb]]+" ");
}
}
return 0;
}
}
I think we should not dweal deep into the number theory and the solution could me much simpler -
public static void findCombination(Set num, Set candidate, Set outcome) {
if (outcome.size() == n) printcombination(outcome);
if (candiate.size() == 3) {
if (satisfyCondition(candidate))
return true;
else
return false;
} else {
for(each element in num) {
num = num - item(num(0));
candidate = candiate U item(num(0));
outcome = outcome U item(num(0));
if ( findCombination(num, candiate, outcome) ) {
//extract two items and call recursively
//candiate = candiate - two items
// outcome = outcome - those two
// num = num U those two - push them back
findCombination(num, candiate, outcome) ;
//Same thing for other two combination
findCombination(num, candiate, outcome) ;
}else {
//take new item from num
// remove last from candiate and outcome and push them back to num
//add new item to candiate and outcome
findCombination(num, candiate, outcome) ;
}
}
}
}
here is a property should be noticed:
- nanny October 27, 2012if ai + ... + ai+k mod num == ai+1 + ... + ai+k+1 mod num, (ai+k+1 - ai) mod num == 0
let a = N/k, b = N%k, if solution exist, there should be way to partition numbers in such a way:
1. totally k groups, N%k groups have N/k + 1 numbers each, and (k-N%k) groups have N/k numbers each. The numbers in each group are in the same mod set. (same remainder mod NUM)
2. The sum of k groups' remainder divisible by NUM.
Then algorithm is quite trivial, group numbers by remainder, with b groups of a + 1 numbers and k-b groups of a numbers, check the sum of remainder.