CODEWITHSUNDEEP
javaarrays
David
David

Reputation: 33

How to check divisibility among integer values in a array

Suppose, I have an array or list of integers (without duplicate), say:

int[] = { 35 165 21 5 6 55 7 42}

Now I need to filter the list based on two rules:

  1. Check if a number is divisible by every other number in the array.
  2. If the number is greater than its divisor then keep the greatest one.

Let me explain my problem a bit more:

Suppose I pick 165 in the previous array. Now, 165 is not divisible by 35, 6, 7, 42; but it is divisible by 5 and 55. So, I remove 5 and 55 from the array. Similarly, 21, 6, 7 are also removed. Therefore, my final list is: 165, 35, 42.

I have tried to sort this out with below code:

Set<Integer> MFV = new HashSet<>();
for(i = 0; i < lwd.length; i++)
{
    for(j = i; j < lwd.length; j++)
    { 
        if(i != j && (lwd[i] % lwd[j] == 0 || lwd[j] % lwd[i] == 0))
        {
            if(lwd[i] > lwd[j])
                MFV.add(lwd[i]);
            //else
                //MFV.add((int)lwd[j]);
        } 
    }
}

System.out.println();
for(Iterator<Integer> it = MFV.iterator(); it.hasNext();)
{
    System.out.print(it.next() + " ");
}

But this gives the result 35, 165, 21.

Upvotes: 0

Views: 5404

Answers (2)

janos
janos

Reputation: 124824

Your implementation doesn't work, for two reasons:

  1. You add elements to the non-divisible set too soon: just because the i-th element is divided by the j-th element doesn't mean that the i-th element shouldn't be removed. It only means that the j-th element should be removed. As the loop continues, it's easily possible that the i-th element may have to be removed as well, but it will be too late, as it's already added to the non-divisible set.

  2. The condition lwd[i] > lwd[j] for adding elements in the non-divisible set is not enough: for example x > c * x will never be true, preventing c * x to be ever added to the set.

Depending on the ordering of the numbers, the implementation may give correct result out of sheer luck. It's easy to break it by rearranging the numbers, for example this ordering demonstrates both issues I pointed out above:

int[] lwd = {35, 21, 5, 6, 55, 7, 42, 165};

In this ordering, the program outputs: 35, 21.

That is, 21 is incorrectly added to the set, before 21 vs 42 is considered, which would eliminate 21. This demonstrates the first problem.

The missing 165 demonstrates the second problem: in the lwd[i] > lwd[j] comparison, 165 will always be the 2nd operand because it's at the end of the list, and it's bigger than all other elements, so it will never be added to the non-divisible set.

Here's an alternative version that fixes these issues:

    int[] nums = {35, 21, 5, 6, 55, 7, 42, 165};
    boolean[] removed = new boolean[nums.length];

    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] > nums[j] && nums[i] % nums[j] == 0) {
                removed[j] = true;
            } else if (nums[i] < nums[j] && nums[j] % nums[i] == 0) {
                removed[i] = true;
            }
        }
    }

    for (int i = 0; i < nums.length; ++i) {
        if (!removed[i]) {
            System.out.print(nums[i] + " ");
        }
    }

    System.out.println();

Upvotes: 1

Andreas
Andreas

Reputation: 159260

Your rule 1 is conflicting with your example.

I believe you could restate your problem as "remove all values that are divisible into another value". (Is "divisible into" the right phrase?)

In other words, remove all a where a < b && b % a == 0.

Upvotes: 0

Related Questions