2
\$\begingroup\$

Given three positive numbers A, B, and C. Find the number of positive integers less than D that are divisible by either of A, B or C.

Input format

The 1st argument given is an Integer A. The 2nd argument given is an Integer B. The 3rd argument given is an Integer C. The 4th argument given is an Integer D.

Output Format

Return an Integer X, the number of positive integers that are divisible by either of A, B, or C.

Constraints

1 <= A, B, C, D <= 1e9

For Example

Input:

A = 2

B = 3

C = 4

D = 10

Output:

6

Explanation:

positive numbers less than D that are divisible by either of A, B or C are 2, 3, 4, 6, 8, 9

My approach:

import java.math.BigInteger;

public class Solution {
    public int solve(int A, int B, int C, int D) {
        BigInteger numDivA = BigInteger.valueOf((D - 1)/A);

        BigInteger numDivB = BigInteger.valueOf((D - 1)/B);

        BigInteger numDivC = BigInteger.valueOf((D - 1)/C);

        BigInteger newA = BigInteger.valueOf(A);

        BigInteger newB = BigInteger.valueOf(B);

        BigInteger newC = BigInteger.valueOf(C);

        BigInteger newD = BigInteger.valueOf(D);

        BigInteger limit = new BigInteger("1000000000");

        BigInteger lcmAB = (newA.divide(hcf(newA, newB))).multiply(newB);

        BigInteger lcmAC = (newC.divide(hcf(newA, newC))).multiply(newA);

        BigInteger lcmBC = (newB.divide(hcf(newB, newC))).multiply(newC);

        BigInteger lcmABC = lcmAB.divide(hcf(lcmAB,newC)).multiply(newC);     

        BigInteger numDivAB = newD.subtract(BigInteger.ONE).divide(lcmAB);

        BigInteger numDivBC = newD.subtract(BigInteger.ONE).divide(lcmBC);        

        BigInteger numDivAC = newD.subtract(BigInteger.ONE).divide(lcmAC);

        BigInteger numDivABC = newD.subtract(BigInteger.ONE).divide(lcmABC);                

        BigInteger numTotal = (((((numDivA.add(numDivB)).add(numDivC)).subtract(numDivAB)).subtract(numDivBC)).subtract(numDivAC)).add(numDivABC);

        return (numTotal.mod(limit)).intValue();
    }

    private BigInteger hcf (BigInteger a, BigInteger b) {

        BigInteger hcf = a.gcd(b);

        return hcf;
    }


}

I have the following questions with regards to the above code:

  1. How can I further improve my approach?

  2. Is there a better way to solve this question?

  3. Are there any grave code violations that I have committed?

  4. Can space and time complexity be further improved?

  5. Have I gone too overboard by using BigInteger?

Reference

\$\endgroup\$
2
\$\begingroup\$

1e9 is only 1 billion, which will fit into a standard integer range of 2 billion some.

The hcf function is unexpected, because it's just a wrapper for BigInteger. I think just using the built in GCD function would be better than making your own method that calls a standard function. If it's critical to the algorithm understanding that we think of a highest common factor instead of a greatest common denominator, then keep the function. If you do keep it, though, use the full name instead of an abbreviation i.e. private BigInteger highestCommonFactor.

I looked at your code and expected to see a loop. I'm assuming you've worked out the math to do this without loops, which is good and probably more efficient. But, I don't really know how this would work, and would be worried someone else looking at the code would have the same problem. A code comment indicating what mathematical principles, or even the name of a theorem, would help immensely.

\$\endgroup\$
  • 1
    \$\begingroup\$ thanks for the suggestions. I understood the Math behind the question pretty fast. I was unable to solve it for higher values though. In the end, I used BigIntegers to solve my problem. \$\endgroup\$ – Anirudh Thatipelli Aug 21 '18 at 16:37
1
\$\begingroup\$

I'll begin by answering the easiest question:

Have I gone too overboard by using BigInteger?

Yes. The problem already ensures the variables are in an appropriate range because they are all <= 1e9 and the max value of an int is 2,147,483,647 or 2e9 (source), which is greater than 1e9. Using an int would be more appropriate.

But looking more deeply, I see you have used LCM as part of your algorithm, which is why you have become dependent on BigIntegers. I know LCM is not a necessary part of an algorithm, so I would use an alternative approach. But more on that later...

How can I further improve my approach?

Note I'm using this section to critique your code without fundamentally changing the algorithm.

Stylistically, line breaks in between each line are unnecessary. Instead, I usually tend to group parts together that do similar things (e.g. assignment) or are multiple parts of a certain process (which could later be converted to a function if it's worthwhile, or if a library function already exists doing the thing I'm trying to do).

BigInteger limit = new BigInteger("1000000000");

//...

return (numTotal.mod(limit)).intValue();

This is quite a concerning pair of lines from a clean code perspective. Putting aside that numtotal should not be able to exceed 1e9 by the nature of the problem, i.e. if numtotal were able to exceed 1e9, you should not just modulus the value until it fits into the range. Instead, you should throw an exception if the result is too large.

Without changing the algorithm, there are some other DRY improvements. The first thing I notice is D - 1 is repeated throughout the code. I would probably assign this to a variable called maxValue. I also notice the structure of VAR_1 / gcd(VAR_1, VAR_2) * VAR_2 to get LCM is suitable for an LCM function. Also concerning is the convolutions of A,B,C variable names; I would probably use arrays to allow for unbounded porting of the variables beyond three variables.


Can space and time complexity be further improved?

In terms of efficiency, I think you're doing more a great deal more work than you need to.

My basic idea about how to approach this problem would be:

  • Create an empty sorted set to store factors.
  • Merge the set of factors from A, B, and C with the main set of factors.
  • Remove all the factors that are >= D from the set of factors; this could be very efficient with binary search
  • Return the length of the set of factors.

This approach is probably unnecessarily space inefficient; I can imagine there might be a way to iterate through A, B, and C's factors alternatively and simultaneously, removing duplicates as it goes along and stopping once D is reached. But as a first start, this approach limits the number of times I have to handle generating factors from a number, and allows a simple and clear base from which to build more complexity.

\$\endgroup\$
-3
\$\begingroup\$

Using BigInteger would increase the complexity of the program you can do it simpily.

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to Code Review! While short answers are acceptable would you mind expanding this to give the OP more to work with? simpily is not an English word - did you mean simply? Are you saying that the OP should merely use Integer instead of BigInteger? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Aug 21 '18 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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