CODEWITHSUNDEEP
javaarrays
Anurag
Anurag

Reputation: 1

searching multiple number in given array

have following problem. suppose i have an array number[n] , i want search multiple number , for example i want to search 12, 45 ,1 ,6,8,5, and if every number present array then i can get favorable result. so there is one way , i just pick one element like 7 if it is present in array number[n], then can get inside the loop , and again initialize another loop and check that if second number is in the number[n] , and so on, so here i need same number of loop as the number of searching numbers. so is there is another way to deal with such problem. because it will running time will be polynomial.

here is my code:

import java.util.Scanner;

class Number {

    boolean check(int[] num)

    {

        for (int i = 0; i < 5; i++) {

            if (num[i] == 7) {

                for (j = 0; j < 5; j++) {

                    if (num[j] == 8) {

                        for (int k = 0; k < 5; k++) {

                            if (num[k] == 9) {

                                return true;
                            }

                            else
                                continue;
                        }

                    } else

                        continue;
                }

            } else

                return false;
        }
    }

    public static void main(string [] args)
      {

       Number obj1 = new Number();

        Scanner input =   new Scanner(System.in);

        int [] num =new int[5];

        for(int i=0;i<5;i++)

          num[i] =input.nextInt();

        boolean get ;

       get = obj1.check(num []);

        System.out.print(response);

      }
}

Upvotes: 0

Views: 952

Answers (4)

Daniel Gabriel
Daniel Gabriel

Reputation: 3985

This solution is not the fastest since it does a binary search for every number. Additionally, it has to be sorted first. It would be better to put all your source numbers into a hash set, like in David Wallace's solution. Then each search time is constant instead of depending on the size of your source array.

boolean check(int[] num) {
    int[] toSearch = new int[] { 12, 45, 1, 6, 8, 5 };
    for (int search : toSearch) {
        if (Arrays.binarySearch(num, search) == -1) {
            return false;
        }
    }
    return true;
}

If you want to use a hash set, you could do it like this:

boolean check(Integer[] num) {
    HashSet<Integer> numSet = new HashSet<>(Arrays.asList(num));

    int[] toSearch = new int[] { 12, 45, 1, 6, 8, 5 };
    for (int search : toSearch) {
        if (!numSet.Contains(search)) {
            return false;
        }
    }
    return true;
}

Upvotes: 0

Kate
Kate

Reputation: 1576

Yes, you can dramatically reduce the number of passes. Firstly though, don't hard code you search numbers like that with a separate loop for each. Create one array to store the numbers being searched for and one containing the numbers being searched. Sort each in the same direction, eg ascending order. Create two ints to act as counters, one for each array. Now use a while loop to compare the numbers in each array at the positions the counters are at.

How you advance the counters depends on how the numbers compare. If the number in the array of ones being searched for is larger than the one being searched, you advance the one being searched. If the other way around you advance the one being searched and if equal you advance both and record the match. Keep going until the end of one array is reached.

Using this method you only traverse the arrays a maximum of one time. I'd write example code but I'm typing on my phone!

Upvotes: 0

Sean
Sean

Reputation: 4470

If you want a sub-polynomial solution then there are a few possibilities.

1) Sort both lists, then loop like so (pseudocode)

toFind = <first element of listToFind>
for i in listToSearch:
  if i == toFind:
    if toFind is last element of listToFind:
      return true
    toFind = next element of listToFind
  else if i > toFind:
    return false

2) Put all the elements of the list to search in a HashSet. Then loop over the elements you want to find and see if it's in the HashSet. If they all are then they're all in the list. If not then they're not all in the list. HashSet has fast lookup, so it will likely be better than polynomial time.

and since I was already beaten to the punch for 2, I'll stop thinking of alternatives and post.

Upvotes: 0

Dawood ibn Kareem
Dawood ibn Kareem

Reputation: 79838

You could do something like this.

public static boolean allFoundIn( int[] toSearch, int... numbers )
    Set numbersSet = new HashSet(Arrays.asList(numbers));
    numbersSet.removeAll(Arrays.asList(toSearch));
    return numbersSet.isEmpty();
}

Then in your main, just call

allFoundIn(num, 7, 8, 9);

which will return true if 7, 8 and 9 are all found in the array num.

Upvotes: 2

Related Questions