How to determine if numbers in an array list if divisible by the numbers in another array list?

Question

I am trying to determine if the numbers in an array list are divisiable by all of numbers in antoher arraylist. My code below outputs all of the numbers from the listdiv list that are disible by any divisors in the listdivisor. I would like to output the values that are divisible by all divisiors in the list not any of them. For example If I have listdiv = [1,2,3,,5,8] and listdivisor= [2,4]. the expected output should be 8 , but this code outputs 2 and 8 .

Thank you !your effort will be greatly appreciated!

for (int i = 0; i < listdiv.size(); i++) {
            for (int c = 0; c < listdivisor.size(); c++) {
                if (listdiv.get(i) % listdivisor.get(c) == 0) {
                System.out.println("final results are :  " + listdiv.get(i));
                }
            }
        }

score 5 · Answer 1 · answered Dec 05 '16 at 07:06

5

Other way with java 8:

List<Integer> collect = listdiv.stream().filter(p ->
        listdivisor.stream().allMatch(d -> p % d == 0)
).collect(Collectors.toList());

Or better performance with parallelStream():

List<Integer> collect = listdiv.parallelStream().filter(p ->
        listdivisor.parallelStream().allMatch(d -> p % d == 0)
).collect(Collectors.toList());

answered Dec 05 '16 at 07:06

Viet

3,349
1
16
35

Parallel would actually be *slower* when the input lists are this small. Still, upvote for Java 8 stream solution. – Andreas Dec 05 '16 at 07:21

Tim Biegeleisen · Accepted Answer · 2016-12-05T07:02:29.297

Your error appears to be caused by that you were counting a dividend as being divisible by all divisors upon hitting the first matching divisor. Instead, you need to add logic which keeps track of all divisors and ensures that each one works with a given dividend.

System.out.println("final results are: ");

for (int i=0; i < listdiv.size(); i++) {
    boolean isDivisible = true;
    for (int c=0; c < listdivisor.size(); c++) {
        if (listdiv.get(i) % listdivisor.get(c) != 0) {
            isDivisible = false;
            break;
        }
    }

    if (isDivisible) {
        System.out.println(listdiv.get(i));
    }
}

score 2 · Answer 3 · answered Dec 05 '16 at 06:56

Your condition checks for values divisible by at least a single divisor, which is not what you want.

You need to check all the divisors before generating output :

for (int i = 0; i < listdiv.size(); i++) {
    boolean divisible = true;
    for (int c = 0; c < listdivisor.size() && divisible; c++) {
        if (listdiv.get(i) % listdivisor.get(c) != 0) {
            divisible = false;
        }
    }
    if (divisible) {
        System.out.println("final results are :  " + listdiv.get(i));
    }
}

Thank you , your code works as well, but i can only tick one asnwer! — gqli, Dec 05 '16 at 07:20

score 2 · Answer 4 · edited May 23 '17 at 11:52

2

In the below solution I continue the outer for loop when an element from the first list is not divisible to any in the second list. If no such case happens the println will get called.

outer: 
for (int i = 0; i < listdiv.size(); i++) {
    for (int c = 0; c < listdivisor.size(); c++) {
        if (listdiv.get(i) % listdivisor.get(c) != 0) {
            continue outer;
        }
    }
    System.out.println("Found :  " + listdiv.get(i));
}

This solution doesn't need any extra variables (such as a boolean to keep status of divisibility) and uses the less known loop labels

edited May 23 '17 at 11:52

Community

1
1

answered Dec 05 '16 at 06:58

Alexandru Severin

6,021
11
48
71

Thank you , your code works as well, but i can only tick one asnwer! – gqli Dec 05 '16 at 07:20

score 2 · Answer 5 · edited May 23 '17 at 11:52

2

All the algorithms presented so far are O(N*M). It is possible to get O(N+M) by first finding the LCM of the first list and using that to filter the second list.

int thelcm = 1
for(int i : listdivisor) {
  thelcm = lcm(thelcm, i);
}

ArrayList<Integer> result = new ArrayList<>();
for(int j : listdiv) {
  if( j % thelcm == 0 ) {
    result.put(j);
  }
}

edited May 23 '17 at 11:52

Community

1
1

answered Dec 05 '16 at 07:08

Michael Anderson

70,661
7
134
187

Sachin Mesare · Answer 6 · 2016-12-05T07:17:36.937

We can use Set for getting the expected output, I have modified your code,

Set<Integer> firstIteration = new HashSet<>();
        Set<Integer> nextIteration = new HashSet<>();
        for (int c = 0; c < divisors.size(); c++) {
            for (int i = 0; i < numbers.size(); i++) {
                if (numbers.get(i) % divisors.get(c) == 0) {
                    if (c == 0) {
                        firstIteration.add(numbers.get(i));
                    } else {
                        nextIteration.add(numbers.get(i));
                    }
                }

            }
            if (c != 0) {
                // We will perform Set intersection here for each iteration
                firstIteration.retainAll(nextIteration);
            }
        }
        System.out.println(firstIteration);

Hope this will solve your issue

How to determine if numbers in an array list if divisible by the numbers in another array list?

6 Answers6