Sum by Factors in Java

The challenge

Given an array of positive or negative integers

I= [i1,..,in]

you have to produce a sorted array P of the form

[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]

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)"
Code language: JavaScript (javascript)

[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); } }
Code language: Java (java)

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)); } }
Code language: Java (java)

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(); } }
Code language: Java (java)

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); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments