check if the numbers in the array between 0-array.length -1

Question

I need to write a program that will check that all the numbers inside the array will be between 0 to array.length-1, and will occur just once, returning true or false.

For example [0,1,3,2] will return True, and [4,3.0,1] and [0,1,2,2] will both return False.

I've try to write it :

public static boolean isPermutation (int[] array) {
    boolean isPermutation =true ;
      for (int i = 0 ; i<array.length & isPermutation; i = i+1) {
          for (int j = 1 ; j<array.length & isPermutation; j = j+1) {
              if (array[i]==array[j]|(array[i]>=array.length)) {
                  isPermutation =false ;
              }
          }
      }
      return isPermutation ;
}

the problem is that when we check array[i]==array[j] its equal when i equals j and not the numbers in the array.

Can anyone help please?

Answer 1

By using a Set you can easily check if there are the same numbers inside the array, because a set stores only 1 occurrence of each number and then in one loop you check if all the numbers are in the range 0..array.length-1:

public static boolean isPermutation (Integer[] array) {
    int length = array.length;

    Set<Integer> set = new HashSet<Integer>(Arrays.asList(array));
    if (set.size() < length)
        return false;

    for (int x : array) {
        if ((x < 0) || (x > length - 1))
            return false;
    }

    return true;
}

public static void main(String[] args) {
    Integer[] a = {0, 1, 3, 2};
    Integer[] b = {0, 1, 3, 1};
    Integer[] c = {0, 1, 3, -1};

    System.out.println(isPermutation(a));
    System.out.println(isPermutation(b));
    System.out.println(isPermutation(c));
}

will print:

true
false
false

Or even better avoid the loop by filtering the Set to a List with only the valid values and check the list's size if it is equal to the array's length:

public static boolean isPermutation (Integer[] array) {
    int length = array.length;
    Set<Integer> set = new HashSet<Integer>(Arrays.asList(array));
    if (set.size() < length)
        return false;
    List<Integer> list = set.stream().filter(x -> x >= 0 && x < length).collect(Collectors.toList());
    return list.size() == length;
}

Answer 2

You can avoid for loop within a for loop and can use mathematics to your advantage and keep adding all the numbers and finally check if the actual sum is equal to the intended sum then return true else false. If all the numbers are withing range and exactly appear once, only then their sum will be equal to the sum of all numbers 1 to N. Meanwhile while scanning the numbers in array, if you encounter any number greater than array length - 1 or less than zero, you can immediately return false.

Here is the kind of code that may help.

public static boolean areNumbersInclusive(int[] arr) {
    long sum = 0;

    for (int n : arr) {
        if (n > arr.length - 1 || n < 0) {
            return false;
        }
        sum += n;
    }

    long intendedSum = ((arr.length - 1) * arr.length) / 2; // sum from 1 to n is n*(n+1)/2

    return intendedSum == sum;
}

public static void main(String args[]) {
    int[] arr1 = {1,0,5,3,2,4};
    int[] arr2 = {1,0,3,4};
    int[] arr3 = {-1,0,3,2};
    int[] arr4 = {1,0,3,2};

    System.out.println(areNumbersInclusive(arr1));
    System.out.println(areNumbersInclusive(arr2));
    System.out.println(areNumbersInclusive(arr3));
    System.out.println(areNumbersInclusive(arr4));
}

This prints following output as expected.

true
false
false
true

Here is OP's correct version of method, although nested for loop can be avoided with my answer.

public static boolean isPermutation(int[] array) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] >= array.length || array[i] < 0) {
            return false;
        }
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) {
                return false;
            }
        }
    }

    return true;
}