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)"

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