wilsonmarriel
BAN USER
Here is my solution in Java:
package random;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class SumOfThreeEqualsZero {
static void getSumZero(Integer[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
Integer key = nums[i];
if (map.containsKey(key))
map.put(key, map.get(key) + 1);
else
map.put(key, 1);
}
List<String> list = new ArrayList<String>();
// to get just one permutation of (i, j k) we will assume i <= j <= k
for (Integer i : map.keySet()) {
for (Integer j : map.keySet()) {
if (j >= i) {
if (i == j && i == 0) {
// i == j == k == 0 case
int count_i = map.get(i);
int count_i_choose_3 = count_i * (count_i - 1) * (count_i - 2) / 6;
for (int m = 0; m < count_i_choose_3; m++) {
list.add("[0, 0, 0]");
}
} else if (i == j) {
// i == j < k case
Integer k = -(i + j);
if (k > j) {
int count_i = map.get(i);
int count_i_choose_2 = count_i * (count_i - 1) / 2;
if (map.containsKey(k)) {
int times = count_i_choose_2 * map.get(k);
for (int m = 0; m < times; m++) {
list.add("[" + i + ", " + j + ", " + k + "]");
}
}
}
} else if (j > i) {
Integer k = -(i + j);
if (k == j) {
// i < j == k case
int count_j = map.get(j);
int count_j_choose_2 = count_j * (count_j - 1) / 2;
int times = count_j_choose_2 * map.get(i);
for (int m = 0; m < times; m++) {
list.add("[" + i + ", " + j + ", " + k + "]");
}
} else if (k > j && map.containsKey(k)) {
// i < j < k case
int times = map.get(i) * map.get(j) * map.get(k);
for (int m = 0; m < times; m++) {
list.add("[" + i + ", " + j + ", " + k + "]");
}
}
}
}
}
}
for (String str : list) {
System.out.println(str);
}
}
public static void main(String[] args) {
Integer[] a = { 2, 3, 1, -2, -1, 0, 2, -3, 0 };
getSumZero(a);
}
}
My solution is similar to dalvik_king's solution:
It generates 25 numbers (0 - 24) with same probability and since 21 = 3*7 and 25-21 = 4 we discard these 4 numbers (by trying again) and return x%7 where x is between 0 and 20 and for each possible result modulus 7 (0-6) we have 3 possibilities, so the probability is the same.
static public int rand7() {
result = 0;
while (result >= 21)
result = rand5()*5 + rand5();
return result%7;
}
here is an O(n) simple solution:
static void sort(int[] a, int[] x) {
for (int i = 0; i < a.length; i++) {
while (a[i] - 1 != i)
doubleSwap(a, a[i] - 1, i, x);
}
}
static void doubleSwap(int[] a, int i, int j, int[] x) {
int aux = a[i];
a[i] = a[j];
a[j] = aux;
aux = x[i];
x[i] = x[j];
x[j] = aux;
}
Repmarkhmitchell6, Analyst at ASAPInfosystemsPvtLtd
At first, tattooing was a hobby kind of thing for me. I didn’t spend too much time in tattoo ...
Repmarkhlee8, Research Scientist at Bank of America
I am a cooking Instructor in New York USA, I Have a degree from the prestigious Culinary Arts Institute of ...
Repjosiredhima, AT&T Customer service email at Aricent
I am an architect with three years experience planning and designing commercial buildings. I am working as principal architect on ...
Repjuanajcox4, Python Developer at Axiom Sources
I have 2 years of experience in designing and implementing computer algorithms or models for creating, displaying, and processing various ...
Repkristyrsharp0, AT&T Customer service email at ABC TECH SUPPORT
I love exploring facts about hvac maintenance services brampton. Operated a service repair and maintenance, answered client questions about the ...
Repsusiejcrider, Member Technical Staff at Accolite software
I was a Communications Consultant with experience in working across various clients .technology, consumer, hospitality, financial services and corporate social ...
Repclairetsmith49, AT&T Customer service email at ADP
Hello, I am Claire and work as a Human resources and I am responsible for recruiting, screening, interviewing and how ...
Thanks PJ, that's right. Let this one pass.
- wilsonmarriel April 22, 2014