0
$\begingroup$

This is my homework question

Given an array A[1..n] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that A[i] + A[j] = α for a given value α.

Give an O(n^2) algorithm to solve the problem.

Can anyone understand what the question like to ask?

$\endgroup$

1 Answer 1

1
$\begingroup$

This problem is called two-sum you should return indices of the two numbers such that they add up to the target.

let's say you have an array called nums = [2,7,11,15] and the target = 9, you should find two indices of two numbers in this example will be

num[0] + num[1] => 2+7 = 9 which is the target

There are two different approaches to solve it, first by brute force and the time complexity will be o(n ^ 2)

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return [i, j]
            }
        }
    }
};

and the second approach by using Hash-table and the time complexity will be o(n) and it's absolutely better

var twoSum = function(nums, target) {
    const indices = new Map();

    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];

        if (indices.has(complement)) {
            return [indices.get(complement), index]
        }

        indices.set(nums[index], index)
    }
};

Note: This solution by using JS language you can write it with any language, just you should understand the problem and the idea of solution and you'll be able to write it with any language you want.

$\endgroup$
1
  • 3
    $\begingroup$ I think it would be better to write the code as an algorithm (psudocode) instead of code in a specific language. That way, its easier to read - and even people who don't know JS can understand it. $\endgroup$
    – nir shahar
    Oct 20, 2021 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.