Sum fractions given 2 arrays - O(n)?

Question

You are given 2 int arrays.

                    A=[1,   2,   1]
                    B=[2,   3,   3]

    so fractions are: 1/2, 2/3,  1/3

A is numerator, B is denominator. so fractions are: 1/2, 2/3, 1/3

Find all pairs that sum upto 1.

Example: here we have 2/3 + 1/3 = 1, so count = 1

return 1

return modulo 10^9 +7 since input can be large

I did it in O(n^2) by going through it once and then computing addition of the 2 and checking if its one and updating counter.

is possible in O(n)?

Any language idm example:

  function solution(integer array A, integer array B){
    return integer_counter;
  }

Make a hash table where you store the fraction `n` with the key `1-n`. Whenever you calculate a new fraction, first look if it already matches a key. Otherwise insert it as a new element with key `1-n`. — Blaze, Oct 28 '19 at 15:01
Are you sure you are calling it `O(n^2)` correctly? It should be `O(2n)` based on what you said. I do not see a nested for loop — ycx, Oct 28 '19 at 15:03
Once ratio are sorted, it can be done in O(n). Alternatively, with hash, it can be done in O(n). — Jarod42, Oct 28 '19 at 15:04
@ycx at each index i look through the whole array and compare each one against the index im at and check if the sum is one. so one loop for each index and nested to check each index against all values — Questions, Oct 28 '19 at 15:05
@DetectivePikachu thats what i did. the j=i+1 part. is that O(n)? i thought that was improved O(n^2) but still O(n^2) — Questions, Oct 28 '19 at 15:08
how can this task be done in O(n), when each sum combination might be 1? 1/2 + 2/4 is also 1 — Lecagy, Oct 28 '19 at 15:13
@DetectivePikachu: your proposal would be `O(n²/2)` so it is still `O(n²)`. — Jarod42, Oct 28 '19 at 15:13
@DetectivePikachu This is just an example. The instructions say "input can be large". — molbdnilo, Oct 28 '19 at 15:17
@Lecagy: We just have to count them, not display them. and in that case, we have up to `n²/4` pair, we can **find** in lower complexity than displaying them. — Jarod42, Oct 28 '19 at 15:18
@DetectivePikachu this is an example, if those values were fixed, there is no need to write code. just to demonstrate how the task works — Lecagy, Oct 28 '19 at 15:19
@DetectivePikachu You would access one element once, two of them twice, three of them thrice, and so on, and 1 + 2 + ... + n = n*(n+1)/2, which is O(n²). — molbdnilo, Oct 28 '19 at 15:19
@Lecagy: indeed, we might have `n²` resulting pairs when all ratios are `1/2`. — Jarod42, Oct 28 '19 at 15:32

score 0 · Answer 1 · edited May 16 '21 at 11:50

This is a C# solution using Dictionary

public static int SumOfFraction(int[] numerator, int[] denominator) {
  int count = 0;
  Dictionary < int, List < int >> keyValuePairs = new Dictionary < int, List < int >> ();

  for (int i = 0; i < denominator.Length; i++) {
    if (keyValuePairs.ContainsKey(denominator[i])) {
      keyValuePairs[denominator[i]].Add(numerator[i]);
    } else {
      keyValuePairs.Add(denominator[i], new List < int > {
        numerator[i]
      });
    }
  }

  foreach(var keypair in keyValuePairs) {
    if (keypair.Key == keypair.Value.Sum()) {
      count++;
    }
  }

  return count;
}

Norhther · Answer 2 · 2021-05-16T23:56:33.450

Cpp solution:

#include <cassert>
#include <cstdint>
#include <unordered_set>
#include <utility>
#include <vector>
#include <iostream>
using namespace std;

//From https://stackoverflow.com/questions/15160889/how-can-i-make-an-unordered-set-of-pairs-of-integers-in-c
struct IntPairHash {
  size_t operator()(const pair<uint32_t, uint32_t> &p) const {
    assert(sizeof(size_t)>=8);  //Ensure that std::size_t, the type of the hash, is large enough
    //Shift first integer over to make room for the second integer. The two are
    //then packed side by side.
    return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
  }
};


size_t 
countPairs(const vector<int>& v1, const vector<int>& v2) {
    unordered_set< std::pair<int, int>, IntPairHash> searchSet;
    size_t count = 0;
    for (size_t i = 0; i < v1.size(); i++) {
        int complement = v2[i] - v1[i];
        if (searchSet.find({complement, v2[i]}) != searchSet.end()) {
            count++;
        }
        searchSet.insert({v1[i], v2[i]});
    }
    return count;
}


int main() {
    cout << countPairs({1,2,1}, {2,3,3});
}

Some remarks of the problem:

You can't store the double value of the division as some comments proposed, because of Floating-point errors
You can't store pair<T1,T2> directly in a unordered_set, because there is no hash function for it.

So I copied a hash function that I found in SO, and then I did the following:

For each pair of v1 and v2, I calculated which number should I find that sums 1. If the value that I'm searching is already in the searchSet, I can add one to the counter. Finally, I add the v1[i], v2[i] value to the searchSet.

The for loop is O(n), and every operation of insertion/check on an unordered_set is O(1).

Sum fractions given 2 arrays - O(n)?

2 Answers2