Hackerrank - Between Two Sets

Hackerrank – Popis problému

Celý popis zadania sa nacháza – Hackerrank.

Riešenie

Vytvorim si pole všetkých pozitívnych čísel, ktoré spĺňajú podmienky úlohy. Bude obsahovať prvky od

$1$

$100$

. Pre všetky tieto prvky zistím, či pre všetky $n % a_i == 0$ a $b_i % n == 0$ . Vypíšem počet takých čísel.

Počiatočné pole sa dá zmenšiť. Bude obsahovať len čísla od $max(A)$ po $min(B)$ (vrátane). Preto lebo: ak má byť $n$ deliteľné všetkými z $A$ – menšie ako $a$ nemôže byť deliteľné najvačším z $A$ , lebo vždy bude zvyšok.
Podobne platí pre $min(B)$ . Ak by bolo väčšie ako $min$ , vždy by dávalo zvyšok po delení pre najmenšie číslo z $B$

Vytvoril som riešenie v týchto programovacích jazykoch:

Scala
Java
Javascript
Ruby

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Scala

import scala.io.Source

object BetweenTwoSets extends App {
  val lines = Source.stdin.getLines().toList
  val a = lines(1).split(" ").map(_.toInt)
  val b = lines(2).split(" ").map(_.toInt)
  val allNumbers = (a.max to b.min).toList

  val x = allNumbers.filter(num => a.forall(i => num % i == 0) && b.forall(j => j % num == 0))
  println(x.size)
}

import scala.io.Source

object BetweenTwoSets extends App {

val lines = Source.stdin.getLines().toList

val a = lines(1).split(" ").map(_.toInt)

val b = lines(2).split(" ").map(_.toInt)

val allNumbers = (a.max to b.min).toList

val x = allNumbers.filter(num => a.forall(i => num % i == 0) && b.forall(j => j % num == 0))

println(x.size)

}

Java

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class BetweenTwoSets {

    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        String firstLine = stdin.nextLine();
        List<integer> a = Arrays.stream(stdin.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());
        List<integer> b = Arrays.stream(stdin.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());
        int aMax = a.stream().max((Integer o1, Integer o2) -> o1 - o2).get();
        int bMin = b.stream().min((Integer o1, Integer o2) -> o1 - o2).get();
        List<integer> result = IntStream.range(aMax, bMin + 1).filter(num -> a.stream().allMatch(i -> num % i == 0) && b.stream().allMatch(j -> j % num == 0))
                .mapToObj(i -> i).collect(Collectors.toList());
        System.out.println(result.size());
        stdin.close();
    }
}
</integer></integer></integer>

import java.util.*;

import java.util.stream.Collectors;

import java.util.stream.IntStream;

public class BetweenTwoSets {

public static void main(String[] args) {

Scanner stdin = new Scanner(System.in);

String firstLine = stdin.nextLine();

List<integer> a = Arrays.stream(stdin.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());

List<integer> b = Arrays.stream(stdin.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());

int aMax = a.stream().max((Integer o1, Integer o2) -> o1 - o2).get();

int bMin = b.stream().min((Integer o1, Integer o2) -> o1 - o2).get();

List<integer> result = IntStream.range(aMax, bMin + 1).filter(num -> a.stream().allMatch(i -> num % i == 0) && b.stream().allMatch(j -> j % num == 0))

.mapToObj(i -> i).collect(Collectors.toList());

System.out.println(result.size());

stdin.close();

}

</integer></integer></integer>

Javascript

'use strict';

const range = (start, end) => {
    const ret = [];
    for(let i = start; i <= end; i++) {
        ret.push(i);
    }
    return ret;
}

const processData = input => {
    const lines = input.split('\n');
    const a = lines[1].split(' ').map(i => parseInt(i));
    const b = lines[2].split(' ').map(i => parseInt(i));
    const aMax = Math.max(...a);
    const bMin = Math.min(...b);
    const result = range(aMax, bMin).filter(num => a.every(i => num % i === 0) && b.every(j => j % num === 0));
    console.log(result.length);
};

process.stdin.resume();
process.stdin.setEncoding("ascii");

let _input = "";
process.stdin.on("data", input => _input += input);
process.stdin.on("end", () => processData(_input));

'use strict';

const range = (start, end) => {

const ret = [];

for(let i = start; i <= end; i++) {

ret.push(i);

}

return ret;

}

const processData = input => {

const lines = input.split('\n');

const a = lines[1].split(' ').map(i => parseInt(i));

const b = lines[2].split(' ').map(i => parseInt(i));

const aMax = Math.max(...a);

const bMin = Math.min(...b);

const result = range(aMax, bMin).filter(num => a.every(i => num % i === 0) && b.every(j => j % num === 0));

console.log(result.length);

};

process.stdin.resume();

process.stdin.setEncoding("ascii");

let _input = "";

process.stdin.on("data", input => _input += input);

process.stdin.on("end", () => processData(_input));

Ruby

(n, m) = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
a_max = a.max
b_min = b.min
all_numbers = (a_max..b_min).to_a
result = all_numbers.select do |num|
  factor_of_a = a.all? { |i| num % i == 0 }
  factor_of_b = b.all? { |j| j % num == 0 }
  factor_of_a && factor_of_b
end

puts result.size

(n, m) = gets.split.map(&:to_i)

a = gets.split.map(&:to_i)

b = gets.split.map(&:to_i)

a_max = a.max

b_min = b.min

all_numbers = (a_max..b_min).to_a

result = all_numbers.select do |num|

factor_of_a = a.all? { |i| num % i == 0 }

factor_of_b = b.all? { |j| j % num == 0 }

factor_of_a && factor_of_b

end

puts result.size

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Between Two Sets