3
\$\begingroup\$

An integer m is defined to be an even subset of another integer n if every even factor of m is also a factor of n.

  • 18 is an even subset of 12 because the even factors of 18 are 2 and 6 and these are both factors of 12.
  • But 18 is not an even subset of 32 because 6 is not a factor of 32.

I wrote the following code to check for even subsets.

public class EvenSubset {
public static void main(String args[]) {
    System.out.println("The result is: " + isEvenSubset(18, 32));
}
public static boolean isEvenSubset(int m, int n) {
    boolean status = false;
    int firstNumber = 0;
    int secondNumber = 0;
    for(int i = 2; i < m ; i++) {
        if(( m % i == 0) && (i % 2 == 0)) {
            firstNumber = i;
            for(int j  = 2;  j < n ; j++) {
                if( (n % j == 0) && (j % 2 == 0)){
                    secondNumber = j;
                    if(firstNumber == secondNumber) {
                        status = true;
                        break;
                    } else {
                        status = false;

                    }
                }

        }
       if(!status){
           status = false;
       } 

    }

}
    return status;
}
 }
\$\endgroup\$
7
  • \$\begingroup\$ 18 is a factor of 18 too, or do you mean to exclude the number itself? \$\endgroup\$
    – h.j.k.
    Jan 22, 2016 at 3:32
  • 1
    \$\begingroup\$ yes, I mean to exclude 1 and number itself. \$\endgroup\$ Jan 22, 2016 at 3:37
  • \$\begingroup\$ Are the braces in your real code like they are in your question or did you just screw up the formatting when posting here? Anyway, please fix it, it's really hard to read like that. \$\endgroup\$
    – 5gon12eder
    Jan 22, 2016 at 6:32
  • 1
    \$\begingroup\$ @user3789184 When you want to exclude the thing itself use the adjective proper (i.e. proper divisor, proper subterm/subexpression/substring etc.) \$\endgroup\$
    – Bakuriu
    Jan 22, 2016 at 9:26
  • \$\begingroup\$ (What is if (!status) { status = false; } good for?) \$\endgroup\$
    – greybeard
    Jan 22, 2016 at 12:44

3 Answers 3

7
\$\begingroup\$

I thought that this coding style looked familiar… and indeed it is. As I previously remarked, flag variables suck. You shouldn't need a variable like status.

You also don't need firstNumber and secondNumber. They are just the same as i and j, respectively.

In fact, the whole algorithm can be implemented more simply, just translating the problem description directly into code. Iterate through the possible even factors of m. If you find a candidate that is a factor of m but isn't a factor of n, then you can conclude that m is not an even subset of n.

public static boolean isEvenSubset(int m, int n) {
    for (int evenFactor = 2; evenFactor < m; evenFactor += 2) {
        if ((m % evenFactor == 0) && (n % evenFactor != 0)) {
            return false;
        }
    }
    return true;
}

However, there is an optimization that we can do, since factors always occur in pairs. There is also a quick test we can do to immediately detect an obvious result, if m is odd.

public static boolean isEvenSubset(int m, int n) {
    // Optional optimization: m has no even factors
    if (m % 2 != 0) return true;

    int sqrtM = (int)(Math.sqrt(m) + 1);
    for (int evenFactor = 2; evenFactor <= sqrtM; evenFactor += 2) {
        if (m % evenFactor == 0) {
            if (n % evenFactor != 0) {
                return false;
            }
            int otherFactor = m / evenFactor;
            if ((otherFactor % 2 == 0) && (n % otherFactor != 0)) {
                return false;
            }
        }
    }
    return true;
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ There's probably a more efficient solution involving finding the prime factorizations of m and n, but it's not as obvious. \$\endgroup\$ Jan 22, 2016 at 4:16
3
\$\begingroup\$

Every number is a composite of primes

$$ n = \prod \text{prime-factors}(n) $$

A factor of \$n\$ is a product of some non-strict subset of \$\text{prime-factors}(n)\$. Technically speaking it's a sub-multiset, but I'll gloss over that technicality in this answer, here and onwards.

A proper divisor of \$n\$ (you incorrectly use the term "factor") is a product of some strict subset of \$\text{prime-factors}(n)\$.

Consider the proper divisors of \$2n\$.

$$ \text{proper-divisor}(2n) = \text{factors}(n) \cup (2 \cdot \text{proper-divisor}(n)) $$

We know this because the \$\text{prime-factors}\$ of \$2n\$ are just the \$\text{prime-factors}\$ of \$n\$ plus a factor of \$2\$, so the strict subsets of \$\text{prime-factors}(2n)\$ can be separated along those that do include the additional \$2\$ and those that do not.

Ergo we can consider the statement

$$ 2i \in \text{proper-divisor}(2x) \implies 2i \in \text{proper-divisor}(2y) $$

to be equivalent to

$$ (2i \in \text{factors}(x) \lor i \in \text{proper-divisor}(x)) \implies (2i \in \text{factors}(y) \lor i \in \text{proper-divisor}(y)) $$

\$2i \in \text{factors}(x) \implies i \in \text{proper-divisor}(x)\$, so this is just

$$ i \in \text{proper-divisor}(x) \implies i \in \text{proper-divisor}(y) $$

Consider now the proper divisors of some composites

$$ x = \prod_{p \in \text{PRIMES}} p^{k_p} \\ y = \prod_{p \in \text{PRIMES}} p^{k'_p} $$

There are two cases to consider.

  • \$\exists p \in \text{PRIMES}. x = p^{k_p}\$

    In this case the proper divisors of \$x\$ are all of the form \$x = p^t\$ where \$t < k_p\$, so we need to check that \$p^{k_p-1} || y\$.

  • \$\nexists p \in \text{PRIMES}. x = p^{k_p}\$

    In this case each \$p^{k_p}\$ for every prime \$p\$ where \$k_p > 0\$ is a proper divisor of \$x\$, and thus of \$y\$. Therefore \$\forall p \in \text{PRIMES}. k_p \le k'_p\$ and thus we need only \$x || y\$.

Thus the most efficient solution overall would be

  • If \$x\$ and \$y\$ are not both positive, raise an error.

  • If \$x\$ is odd, return true. Otherwise, halve \$x\$.

  • If \$y\$ is odd, return x == 2. Otherwise, halve \$y\$.

  • If y % x == 0, return true.

  • Now the only solution is for \$x = p^{k_p}\$ for some \$p\$. Let p = x / gcd(x, y). gcd is provided by BigInteger.

  • Return isPrime(p) && isPower(p, x). isPrime can be implemented efficiently the vast majority of the time with Java's isProbablePrime and isPower can be implemented sufficiently efficiently through repeated multiplication, or repeated squaring if that ends up slower than primality testing.

Here's an implementation in Rust (which I chose because of the convenient ecosystem)

extern crate num;
extern crate primal;

use num::integer::Integer;
use primal::is_prime;

fn is_power(base: u64, mut value: u64) -> bool {
    while value.is_multiple_of(&base) {
        value /= base;
    }
    value == 1
}

fn even_subset(mut x: u64, mut y: u64) -> bool {
    // See http://codereview.stackexchange.com/a/117601/40768
    // for an explanation of the algorithm.
    assert!(x != 0 && y != 0, "inputs must not be zero");

    if x.is_odd() { return true; }
    x /= 2;

    if y.is_odd() { return x == 2; }
    y /= 2;

    if y.is_multiple_of(&x) {
        return true;
    }

    let p = x / x.gcd(&y);
    is_prime(p) && is_power(p, x)
}
[dependencies]
num = "0.1"
primal = "0.2"

As a great man once said,

Beware of bugs in the above code; I have only proved it correct, not tried it.

\$\endgroup\$
1
\$\begingroup\$

You can iterate up to the square root of m, while bearing in mind to test the other factor:

for (int i = 2; i < (int) Math.sqrt(m); i++) {
    if (m % i == 0) {
        if (i % 2 == 0 || (m / i) % 2 == 0) {
            // ...
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Checking as few factors a possible is an improvement worth aiming for. In addition to a tighter upper bound for the loop, you could try and generate even candidates, only: for (int i = 2, limit = (int) Math.sqrt(m) ; i < limit; i += 2). (I don't quite get the condition of the inner if.) \$\endgroup\$
    – greybeard
    Jan 22, 2016 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.