0

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.

CollinD
  • 7,304
  • 2
  • 22
  • 45
remington howell
  • 148
  • 1
  • 2
  • 13

1 Answers1

1

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).

Grassright
  • 248
  • 3
  • 8
  • Concerning `HashMap map = new HashMap();` and "can be easily converted to C code", [I think you should be more explicit here in step two.](http://imgc-cn.artprintimages.com/images/P-473-488-90/60/6079/KTUD100Z/posters/sidney-harris-i-think-you-should-be-more-explicit-here-in-step-two-cartoon.jpg) – chux - Reinstate Monica Sep 15 '15 at 19:31
  • @chux Alright, in C, the easiest way is to use an int array, with O(n) space complexity. – Grassright Sep 15 '15 at 21:24