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

Question

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.

Looks like this has been asked and answered. stackoverflow.com/questions/9656789/… — CollinD
– CollinD, Commented Sep 15, 2015 at 15:58

Grassright · Accepted Answer · 2015-09-15 21:20:52Z

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

edited Sep 15, 2015 at 21:20

answered Sep 15, 2015 at 15:58

Grassright

2683 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

chux Over a year ago

Concerning HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); and "can be easily converted to C code", I think you should be more explicit here in step two.

Grassright Over a year ago

@chux Alright, in C, the easiest way is to use an int array, with O(n) space complexity.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related