CODEWITHSUNDEEP
javatime-complexity
user15123458
user15123458

Reputation:

Reduce the complexity of a program

How can I reduce the complexity of this code : this code returns true if there are two elements in the array whose sum equals a number K

public static boolean methode(int c, int[] t) {
    for(int i = 0; i < t.length; i++)
        for(int j = 0; j < t.length; j++)
            if(j != i && t[i] + t[j] == c)
                return true;

    return false;
}

Upvotes: 0

Views: 86

Answers (2)

Oleg Cherednik
Oleg Cherednik

Reputation: 18245

As one of the option, you can use Set to store previous numbers. It reduces time complexity from O(n*n) to O(n), but at the same time in increases space complexity from O(1) to O(n).

public static boolean verification(int k, int[] tab) {
    Set<Integer> unique = new HashSet<>();
    
    for(int i = 0; i < tab.length; i++) {
        if(unique.contains(k - tab[i]))
            return true;

        unique.add(tab[i]);
    }

    return false;
}

Upvotes: 2

Viktor T&#246;r&#246;k
Viktor T&#246;r&#246;k

Reputation: 1319

If you want to check the sum of two elements then you can use the following code. It's a bit simpler:

public static boolean verification(int k, int[] tab) {
    for(int i = 0; i < tab.length - 1; i++)
        for(int j = i + 1; j < tab.length; j++)
            if(tab[i] + tab[j] == k)
                return true;

    return false;
}

Upvotes: 0

Related Questions