1

I wrote a function which returns true only if a given array contains at least one integer that can divide all the other integers. Otherwise returns false.

Here's what I've tried:

     public static boolean check(int[] arr) {
         int n = arr.length;
         boolean res = false;
         
         for(int i=0; i<n; i++) {             
             for(int j=0; j<n; j++) {
                if(arr[i]%arr[j]!=0 && arr[j]%arr[i]!=0) break;
                
                if(j == n-1) res = true;
            }
         }
         return res;
     }

     public static void main(String []args){
        int[] arr = {4,2,6,8};
        System.out.println(check(arr)); // -> true
        
        int[] arr2 = {4,3,6,8};
        System.out.println(check(arr2)); // -> false
     }

Seems like my code provides the correct output, but I want to know a better approach without having to use nested for loops.

Rukshan Jayasekara
  • 1,945
  • 1
  • 6
  • 26
  • 7
    I'm not sure, but I *think* if there is such an integer, it must be the smallest, so take the min() and then check if it divides all the numbers. – Mark Lavin Aug 22 '21 at 19:13
  • Already answered here: https://stackoverflow.com/questions/4009198/java-get-greatest-common-divisor#4009247 You're looking for the greatest common divisor (GCD). – gouessej Aug 22 '21 at 19:56
  • @gouessej - If you want to solve it using GCD, it will not only be about finding GCD but also checking if the GCD is present in the array. However, it will be a too complicated way because you will have to find the GCD of not only two numbers but of all the numbers. – Arvind Kumar Avinash Aug 22 '21 at 20:04
  • @ArvindKumarAvinash You're right, my suggestion is over-complicated. – gouessej Aug 22 '21 at 20:09
  • @MarkLavin I think you want the minimum positive absolute value rather than just the minimum. Zero can be divided by any number. – Andy Turner Aug 22 '21 at 20:17

4 Answers4

3

Stream API

For a cleaner solution, I would use Stream API.

import java.util.Arrays;
import java.util.function.Supplier;
import java.util.stream.IntStream;

public class Main {
    public static boolean check(int[] arr) {
        if (arr == null || arr.length == 0)
            return false;
        int[] arrClone = arr.clone();
        Arrays.setAll(arrClone, i -> Math.abs(arrClone[i]));
        Supplier<IntStream> streamSupplier = () -> Arrays.stream(arrClone);
        int min = streamSupplier.get().min().getAsInt();
        return streamSupplier.get().filter(n -> min != 0).allMatch(n -> n % min == 0);
    }

    public static void main(String[] args) {
        int[] arr = { 4, 2, 6, 8 };
        System.out.println(check(arr)); // -> true

        int[] arr2 = { 4, 3, 6, 8 };
        System.out.println(check(arr2)); // -> false

        System.out.println(check(new int[] { 1, -5 }));
        System.out.println(check(new int[] {}));
        System.out.println(check(new int[] { 0, -5 }));
        System.out.println(check(new int[] { 0, 5 }));
    }
}

Output:

true
false
true
false
true
true

Learn more about the Stream API from Processing Data with Java SE 8 Streams, Part 1 and Part 2: Processing Data with Java SE 8 Streams.

Arvind Kumar Avinash
  • 71,965
  • 6
  • 74
  • 110
3

Try this.

public static boolean check(int[] arr) {
    return IntStream.of(arr)
        .filter(i -> i != 0)
        .map(Math::abs)
        .min().stream()
        .anyMatch(min -> IntStream.of(arr)
            .allMatch(i -> i % min == 0));
}

public static void main(String []args){
   System.out.println(check(new int[] {4, 2, 6, 8}));  // true
   System.out.println(check(new int[] {4, 3, 6, 8}));  // false
   System.out.println(check(new int[] {-4, 2, 6, 8})); // true
   System.out.println(check(new int[] {4, 0, 6, 8}));  // false
   System.out.println(check(new int[] {2, 0, 6, 8}));  // true
   System.out.println(check(new int[] {}));            // false
}

output:

true
false
true
false
true
false
0

Let's use the List. So you'll sort the numbers in ascending order, with the first number being the smallest using the Collections.sort() method. Then, just take the first number and check if dividing the next number by the first one returns the remainder 0. If there is a remainder other than 0 in the middle of the for, it means that there is no number capable of dividing all the integers, so it will stop the for and return false.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class YourClass {

    public static boolean check(List<Integer> arr) {
        boolean res = true;

        Collections.sort(arr);
        int pri;

        if(arr.size() > 0){
           pri = arr.get(0);

           for(int i = 1; i < arr.size(); i++){
                if(arr.get(i) % pri != 0){
                    res = false;
                    break;
                }
           }
        }else{
            res = false;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(check(Arrays.asList(4,2,6,8)));

        //or
        List<Integer> list = Arrays.asList(4, 3, 6, 8);
        System.out.println(check(list));
    }

}
Moisés Cunha
  • 141
  • 3
0

Number you looking for is smallest number greater than 0. So you don't need nested loops.

Find the smallest number:

  • if it is 1, you have your answer.
  • if not, you need to go through the list only once.
talex
  • 17,973
  • 3
  • 29
  • 66
  • Well idea of "divisible by" is usually applied to natural numbers, but it is easy to extend this algorithm to negative numbers. – talex Aug 22 '21 at 20:07
  • "Number you looking for is smallest number greater than 1" greater than zero, surely? – Andy Turner Aug 22 '21 at 20:28
  • @AndyTurner yes. I thought that 1 is usually special case and had brain glitch. – talex Aug 22 '21 at 20:39
  • @user16320675 Ok. I'm so old that negative numbers wasn't invented when I studied that, so I have problems with them sometimes. – talex Aug 22 '21 at 20:40