CODEWITHSUNDEEP
javaarrays
Pawan Kalyan
Pawan Kalyan

Reputation: 581

How to find index positions of numbers in an array on a condition?

I have an integer array.. and I will input a number And I have to find out the index positions of two numbers such that the sum of the numbers is equal to the input number.

I did it with the following code

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class FindIndex {

    int a[] = { 1, 7, 6, 5, 12, 2, 3, 11 };

public void findingIndex() {
    Arrays.sort(a);
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the sum of two selected numbers from the array");
    int i = sc.nextInt();
    for(int j=0;j<a.length;j++){
        for(int k=j+1;k<a.length;k++){
            if(a[j]+a[k]==i){
                System.out.println(Arrays.toString(a));
                System.out.println("The indexes of the elements are"+j+"and"+k);
            }
        }
    }


}

public static void main(String[] args) {
    FindIndex fi = new FindIndex();
    fi.findingIndex();
    System.out.println("end of the program");
}

}

The output is 

Enter the sum of two selected numbers from the array
14
[1, 2, 3, 5, 6, 7, 11, 12]
The indexes of the elements are1and7
[1, 2, 3, 5, 6, 7, 11, 12]
The indexes of the elements are2and6
end of the program

Now i want to achieve this using only one for loop??How to do?

Upvotes: 0

Views: 2944

Answers (3)

user2336315
user2336315

Reputation: 16067

Since your array is already sorted, you can create two indexes, one starting from the begining and one from the end. If the current sum is inferior than the number to find, increment the first index otherwise decrement the second.

public static void findingIndex() {
         Arrays.sort(a);
         System.out.println(Arrays.toString(a));
         Scanner sc = new Scanner(System.in);
         System.out.println("Enter the sum of two selected numbers from the array");
         int i = sc.nextInt();
         int index1 = 0; 
         int index2 = a.length-1;
         while(index1 != index2){
            int sum = a[index1] + a[index2];
            if(sum == i){
                System.out.println("Found with "+index1+" "+index2);
                index1++;
            }
            else if (sum < i){
                index1++;
            } else {
                index1 = 0;
                index2--;
            }
         }
}

The time taking to sort runs in O(nlogn) and the complexity of the while loop will be O(n), O(n²), but it still use one loop.

So the overall complexity of the algorithm will be O(n²).

This can be easily translated into one for loop :

for(int index1 = 0, index2 = a.length-1; index1 != index2;){
            int sum = a[index1] + a[index2];
            if(sum == i){
                System.out.println("Found with "+index1+" "+index2);
                index1++;
            }
            else if (sum < i){
                index1++;
            } else {
                index1 = 0;
                index2--;
            }
}

Upvotes: 5

Ruchira Gayan Ranaweera
Ruchira Gayan Ranaweera

Reputation: 35557

Any scenario there is a optimum level, we can't simplify further beyond that level. You can try following.

    Integer a[] = { 1, 2, 3, 5, 6, 7, 11, 12} ;
    List<Integer> list=new ArrayList<>();
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the sum of two selected numbers from the array");
    int in = sc.nextInt();
    for(int i=0;i<a.length;i++){
        if(list.contains(in-a[i]) &&(list.indexOf(in-a[i])!=i)){
            System.out.println("The indexes of the elements are"
                                        +i+"and"+list.indexOf(in-a[i]));
        }
    }

But contains() method it self has for-loop.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533492

You can do it in O(n * log n) time this way.

public static int[] findSum(int[] values, int sum) {
    Arrays.sort(values);  // O(N * log N)
    for(int i = 0; i < values.length() - 1; i ++) { // O(n)
        int remainder = sum - values[i];
        // O(log N) and assuming you can't use the same value twice.
        int pos2 = Arrays.binarySearch(value, i + 1, values.length, remainder); 
        if (pos2 >= 0)
            return new int[] { i, pos2 };
    }
    return null;
}

So the total order is O(N log N) + O(N) * O(log N) or just O(N log N)

Upvotes: 6

Related Questions