CODEWITHSUNDEEP
carraysloops
remington howell
remington howell

Reputation: 170

How to scan in and compare values in an array without loops

I have an assignment to do where I need to scan a number of cases. In each case, you're given an array and a target. The goal is to scan the array to find a set of two numbers which add up to the target.

My issue is I need to get my big-oh (the run time) to equal n, which means I can have at most a single loop. This is my code as it stands now.

//Assume that cases, sizeofarray, array, and target already exist.    
while(cases =! 0){
        scanf("%d", @sizeofarray);
        scanf("%d", @target);

        array = malloc(sizeof(int) * sizeofarray);
    }

As you can see the requirement to function for multiple cases already removes my ability to use additional loops within the function. Therefor I need to both scan in and compare values in the array without using a for loop.

I suppose the other option is to not loop with the case value, thereby enabling me to use a loop elsewhere and keeping my big-oh run time below n.

If anybody can help me, I would appreciate it. To reiterate, I need to know if there exists a technique to scan in values into an array without looping, for comparing values in an array without looping, or for scanning multiple cases without looping.

Upvotes: 0

Views: 2252

Answers (1)

Grassright
Grassright

Reputation: 268

This is a classic two sum problem. Use HashMap to store the target value. I am providing a Java sample for your reference. I think it can be easily converted to C++ code

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] result = new int[2];

    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            int index = map.get(numbers[i]);
            result[0] = index+1 ;
            result[1] = i+1;
            break;
        } else {
            map.put(target - numbers[i], i);
        }
    }

    return result;
    }
}

Time complexity depends on the put and get operations of HashMap which is normally O(1).

Time complexity of this solution is O(n).

Upvotes: 1

Related Questions