Electronics Shop - HackerRank Problem

Find the problem definition @ HackerRank

Brute-Force Solution

Using the Brute-Force method, this problem can be solved by considering every possible pairs. If the considered pair gives better result (i.e > max) and satisfies the constraints (i.e. <= s), then we select current pair as the solution. Result is returned after all the pairs have been considered.

  /**
   * Brute Force Solution
   * @param s
   * @param keyboards
   * @param drives
   * @return
   */
  public int getMoneySpent(int s, int[] keyboards, int[] drives) {
    int max = -1;
    for (int i = 0; i < keyboards.length; i++) {
      for (int j = 0; j < drives.length; j++) {
        int amount = keyboards[i] + drives[j];
        if (amount > max && amount <= s ) {
          if (max == s) return max;
          max = amount;
        }
      }
    }
    return max;
  }    
    

Time Complexity

Time Complexity of this solution depends upon the number of pairs considered. Since there are $n\ keyboards$ and $m\ drives$, total of $n \times m$ pairs are considered. Processing time for each pair, as we can see in the code, is constant time operation ${\cal O}(1)$. $\therefore$ The time complexity of this solution is ${\cal O}(n \times m)$. The space complexity is ${\cal O}(1)$ since we haven't use any extra data structure to hold inputs.

Better Solution

The problem could be optimized to solve in better time complexity. We can Sort one of the array and iterate through other array. While iterating through the other array, we apply the Binary Search on the sorted array to obtain the best pair. In order to keep the complexity low (Do the maths on your own ), I am going to sort the array with lower number of elements and iterate over the other one.

/**
   * Computes using Binary Search
   * @param keyboards
   * @param drives
   * @param s
   * @return
   */
  public int getMoneySpent(int[] keyboards, int[] drives, int s) {
    int max = -1;
    int[] larger = keyboards.length > drives.length ? keyboards : drives;
    int[] smaller = keyboards.length > drives.length ? drives : keyboards;

    Arrays.sort(smaller); // O(k logk)

    for (int i = 0; i < larger.length; i++) {  // O(n)
      if (larger[i] < s) {
        int pair = search(smaller, s - larger[i], 0, smaller.length); // O(logk)
        if (pair == -1) continue;
        if (max < smaller[pair] + larger[i]) {
          max = smaller[pair] + larger[i];
        }
      }
    }
    return max;
  } // getMoneySpent
  
  //----------------------------------------------------------------------------------

  /**
   * Searches the best pair using Binary Search
   * @param in
   * @param item
   * @param lo
   * @param hi
   * @return
   */
  public int search(int[] in, int item, int lo, int hi) {
    if (item < in[lo]) return -1;
    while (hi - lo > 1) {
      int midIdx = (lo + hi) / 2;
      if (item == in[midIdx]) return midIdx;
      else if (item > in[midIdx]) {
        lo = midIdx;
      } else {
        hi = midIdx;
      }
    }
    return lo;
  } // search

    

Time Complexity

Time Complexity of the solution depends upon the sorting of smaller array, iteration of larger array and the binary search on the sorted array.

Let, $n =$ Number of Elements in the larger array
       $k =$ Number of Elments in the smaller array

Then,

1. Time Complexity of Sorting = ${\cal O})(k\ logk)$
2. Time Complexity of iteration = ${\cal O}(n)$
3. Time Complexity of Binary Serach = ${\cal O}(logk)$

$\therefore$ The overall Time Complexity is ${\cal O}(k\ logk + n\ logk) \approx {\cal O}(n\ logk)$. The Space Complexity is ${\cal O}(1)$

---

---

---