The challenge
Given an array of positive or negative integers
I= [i<sub>1</sub>,..,i<sub>n</sub>]
you have to produce a sorted array P of the form
[ [p, sum of all i<sub>j</sub> of I for which p is a prime factor (p positive) of i<sub>j</sub>] ...]
P will be sorted by increasing order of the prime numbers. The final result has to be given as a string in Java, C#, C, C++ and as an array of arrays in other languages.
Example:
I = {12, 15}; // result = "(2 12)(3 27)(5 15)"
[2, 3, 5] is the list of all prime factors of the elements of I, hence the result.
Notes:
- It can happen that a sum is 0 if some numbers are negative!
Example: I = [15, 30, -45] 5 divides 15, 30 and (-45) so 5 appears in the result, the sum of the numbers for which 5 is a factor is 0 so we have [5, 0] in the result amongst others.
- The returned string is not permitted to contain any redundant trailing whitespace: you can use dynamically allocated character strings.
The solution in Java code
Option 1:
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SumOfDivided {
public static String sumOfDivided(int[] l) {
final int maxValue = Arrays.stream(l).map(num -> Math.abs(num)).max().getAsInt();
return eratosteneSieve(maxValue).stream()
.reduce("",
(resultString, primeNum) -> {
List<Integer> divisibleNum = Arrays.stream(l).filter(num -> num % primeNum == 0).boxed().collect(Collectors.toList());
return divisibleNum.size() > 0
? resultString + String.format("(%d %d)", primeNum, divisibleNum.stream().mapToInt(Integer::intValue).sum())
: resultString;
},
(not, used) -> null);
}
public static List<Integer> eratosteneSieve(final int x) {
final List<Integer> candidates = IntStream.rangeClosed(2, x).boxed().collect(Collectors.toList());
return candidates.stream()
.filter(num -> num <= Math.sqrt(x))
.reduce(candidates,
(resList, currNum) -> resList.stream()
.filter(num -> num % currNum != 0 || num.equals(currNum))
.collect(Collectors.toList()),
(not, used) -> null);
}
}
Option 2:
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.*;
import static java.util.Arrays.*;
public class SumOfDivided {
public static String sumOfDivided(int[] l) {
return generatePrimeNumbersClosed(stream(l).max().orElse(0))
.mapToObj(it -> new Object(){ int primeNumber = it, sum = stream(l).filter(n -> n % it == 0).sum(); })
.filter(it -> it.sum > 0)
.map(it -> String.format("(%d %d)", it.primeNumber, it.sum))
.collect(joining(""));
}
private static IntStream generatePrimeNumbersClosed(int n) {
BitSet composited = new BitSet();
for(int i = (int) Math.sqrt(n); i >= 2; i--) for(int m = i * i; m <= n; m += i) {
composited.set(m);
}
return IntStream.rangeClosed(2, n).filter(it -> !composited.get(it));
}
}
Option 3:
import java.util.*;
public class SumOfDivided {
public static String sumOfDivided(int[] l) {
Map<Integer, Integer> map = new HashMap<>();
for (int number:l) {
int i = number < 0 ? -number:number;
for(int j = 2; j <= i; j++) {
if (i%j == 0) map.put(j, map.get(j) == null ? number : map.get(j)+number);
while(i%j == 0) i /= j;
}
}
return map.entrySet().stream()
.sorted(Comparator.comparing(Map.Entry::getKey))
.map(e -> String.format("(%d %d)",e.getKey(),e.getValue()))
.reduce((x,y) -> x+y)
.get();
}
}
Test cases to validate our solution
import static org.junit.Assert.*;
import org.junit.Test;
import java.util.Arrays;
public class SumOfDivTest {
private static void testing(int[] arr, String exp) {
System.out.println("Testing " + Arrays.toString(arr));
String ans = SumOfDivided.sumOfDivided(arr);
System.out.println("Actual " + ans);
System.out.println("Expect " + exp);
assertEquals(exp, ans);
System.out.println("#");
}
@Test
public void test() {
int[] lst = new int[] {12, 15};
testing(lst, "(2 12)(3 27)(5 15)");
lst = new int[] {15,21,24,30,45};
testing(lst, "(2 54)(3 135)(5 90)(7 21)");
lst = new int[] {107, 158, 204, 100, 118, 123, 126, 110, 116, 100};
testing(lst, "(2 1032)(3 453)(5 310)(7 126)(11 110)(17 204)(29 116)(41 123)(59 118)(79 158)(107 107)");
lst = new int[] {-29804, -4209, -28265, -72769, -31744};
testing(lst, "(2 -61548)(3 -4209)(5 -28265)(23 -4209)(31 -31744)(53 -72769)(61 -4209)(1373 -72769)(5653 -28265)(7451 -29804)");
lst = new int[] {17, -17, 51, -51};
testing(lst, "(3 0)(17 0)");
lst = new int[] {173471};
testing(lst, "(41 173471)(4231 173471)");
lst = new int[] {100000, 1000000};
testing(lst, "(2 1100000)(5 1100000)");
}
private static int randInt(int min, int max) {
return (int)(min + Math.random() * ((max - min) + 1));
}
private static int[] doEx(int k) {
int i = 0; int[] res = new int[k];
while (i < k) {
int rn = randInt(-100, 500);
if (rn != 0) {res[i] = rn;}
i++;
}
return res;
}
private static String sumOfDivided54(int[] lst) {
int[] rem = new int[lst.length];
int max = 0;
String result = "";
for (int i = 0; i < lst.length; ++i) {
rem[i] = Math.abs(lst[i]);
max = Math.max(max, Math.abs(lst[i]));
}
for (int fac = 2; fac <= max; ++fac) {
boolean isFactor = false;
int tot = 0;
for (int i = 0; i < lst.length; ++i) {
if (rem[i] % fac == 0) {
isFactor = true;
tot += lst[i];
while (rem[i] % fac == 0) {
rem[i] /= fac;
}
}
}
if (isFactor) {
result += "(" + fac + " " + tot + ")";
}
}
return result;
}
@Test
public void test1() {
System.out.println("Random Tests");
for (int i = 0; i < 5; i++) {
int[] v = doEx(randInt(10, 25));
String exp = sumOfDivided54(v);
testing(v, exp);
}
}
}