Sum fractions given 2 arrays - O(n)?

user_9711734 0
Viewed 2344

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;
  }
complexity-theory time-complexity
2 Answers

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;
}
user_121962370

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

user_54046470
Related