Sum by Factors

kata programming

مساله:

آرایه ای از اعداد صحیح مثبت و منفی به شما داده می شود:

I= [i1,..,in]

شما باید آرایه P را به فرم زیر ایجاد کنید:

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

آرایه P باید بر اساس اعداد اول مرتب سازی شود. در آخر باید نتیجه به صورت یک رشته نمایش داده شود.

مثال:

I = {12, 15}; // result = "(2 12)(3 27)(5 15)"

اعداد [2,3,5] لیست اعداد اولی است که در این آرایه استفاده شده است.

نکته:

این امکان وجود دارد که اگر اعداد منفی هم داشته باشیم، جمع اعداد 0 شود.


Description:

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.

In Fortran – as in any other language – the returned string is not permitted to contain any redundant trailing whitespace: you can use dynamically allocated character strings.


راه حل:

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);
    }
}
import java.lang.Math;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.stream.Collectors;

public class SumOfDivided {

  /*
  *  We use a cache of already known primes to minimize double computation.
  */
  private static SortedSet<Integer> primeCache = new TreeSet<>();
  private static Map<Integer, Integer> map = new HashMap<>();

  public static String sumOfDivided(int[] l) {
    initalize();
    
    for(int i=0; i<l.length; i++) {
      int absNum = Math.abs(l[i]);
      updatePrimeCache(absNum);
      updateMap(l[i]);
    }
    
    return convertMapToString();
  }
  
  private static void initalize(){
    map = new HashMap<>();
    if(primeCache.isEmpty()){
      primeCache.add(2);
    }
  }
  
  /*
  *  We update the prime cache so it contains all primes up to number. 
  */
  private static void updatePrimeCache(int number) {
    Integer largestKnownPrime  = primeCache.last();
    if(largestKnownPrime > number) {
      return;
    }
    
    for(int p=largestKnownPrime+1; p <= number; p++) {
      if(isPrime(p)) {
        primeCache.add(p);
        largestKnownPrime = p;
      }
    }
  }
  
  private static boolean isPrime(int p) {
    for(int i=2; i<=Math.sqrt(p); i++) {
      if(p%i == 0) return false;
    } 
    
    return true;
  }
  
  private static void updateMap(int num) {
    for(Integer prime: primeCache) {
      if(num%prime == 0) {
        Integer sum = map.getOrDefault(prime, 0);
        sum += num;
        map.put(prime, sum);
      }
    }
  }
  
  private static String convertMapToString() {
    TreeMap<Integer, Integer> sortedMap = new TreeMap(map); 
    return sortedMap.entrySet()
      .stream()
      .map(entry -> "(" + entry.getKey() + " " + entry.getValue() + ")")
      .collect(Collectors.joining(""));
  }
}
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));
  }
}

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));
  }
}
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class SumOfDivided {
  
  public static String sumOfDivided(int[] l) {
    StringBuilder stringBuilder = new StringBuilder();
    Set<Integer> allPrimeFactorsForElementsOfl = findAllPrimeFactorsForElementsFromArr(l);
    for (Integer primeFactor : allPrimeFactorsForElementsOfl) {
      int sum = 0;
      for (Integer element : l) {
        if (isPrimeFactor(primeFactor, element)) {
          sum += element;
        }
      }
      stringBuilder.append("(" + primeFactor + " " + sum + ")");
    }
    return stringBuilder.toString();
  }

  private static Set<Integer> findAllPrimeFactorsForElementsFromArr(int[] numbers) {
    Set<Integer> primeFactors = new TreeSet<Integer>();
    for (int number : numbers) {
      primeFactors.addAll(findPrimeFactors(Math.abs(number)));
    }
    return primeFactors;
  }

  private static Set<Integer> findPrimeFactors(int numberFromI) {
    Set<Integer> primeFactors = new HashSet<Integer>();
    for (int i = 2; i <= numberFromI; i++) {
      while (numberFromI % i == 0) {
        primeFactors.add(i);
        numberFromI /= i;
      }
    }
    return primeFactors;
  }

  private static boolean isPrimeFactor(int primeFactor, int numberTobeChecked) {
    return numberTobeChecked % primeFactor == 0;
  }

}
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.stream.IntStream;

public class SumOfDivided {
  public static String sumOfDivided(int[] numbers) {
    int maxValue = Arrays.stream(numbers).map(Math::abs).max().getAsInt();
    boolean[] eratosteneSieve = new boolean[maxValue];
    StringBuilder result = new StringBuilder(4*maxValue*numbers.length);
    IntStream.rangeClosed(2, maxValue)
      .filter(num-> !eratosteneSieve[num-2])
      .forEach(prime->{
        for(int i=2; prime*i <= maxValue; i++){
            eratosteneSieve[prime*i-2] = true;
        }
        OptionalInt sum = Arrays.stream(numbers).filter(num-> num % prime == 0).reduce(Integer::sum);
        if(sum.isPresent()){
          result.append("(").append(prime).append(" ").append(sum.getAsInt()).append(")");
        }
      });
    return result.toString();
  }
}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.