Advertisement
sidhartha11

return list/set of pairs of Ints equaling a particular SUM

Mar 7th, 2018
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.18 KB | None | 0 0
  1. package org.geo.scala.fundamentals.examples.numerical
  2. import scala.collection.mutable._
  3. /**
  4. * @author george
  5. * This class will find the number of unique pairs that equal
  6. * to some input sum in an input array
  7. *
  8. * @param a Int array containing numbers to look for pairs in
  9. * @param n Int sum we are trying to find in a
  10. *
  11. */
  12. class PairsSummingToN(val a: Array[Int], val n: Int) {
  13. require(n > 0)
  14. require(a.length > 1)
  15.  
  16. /**
  17. * @return list of pairs that may contain duplicates
  18. */
  19. def getPairsEqualingToSumList(): ListBuffer[(Int, Int)] = {
  20. val listOfPairs = new ListBuffer[(Int, Int)]()
  21. val map: Map[Int, ListBuffer[Int]] = new HashMap[Int, ListBuffer[Int]]()
  22. a.indices.foreach(i => {
  23. val x = -(a(i) - n)
  24. val m = map get x
  25. if (m == None) {
  26. /** put a new map entry into the value of map **/
  27. map += (x -> ListBuffer(i))
  28. } else {
  29. /** get the map out and update it **/
  30. val mi = m.get
  31. mi += (i)
  32. }
  33. val f = map get a(i)
  34. if (f != None) {
  35. val lb = f.get
  36. listOfPairs += ((a(i), a(f.get.apply(f.get.size - 1))))
  37. }
  38. })
  39. listOfPairs
  40. }
  41.  
  42. /**
  43. * @return A unique set of pairs without duplicates
  44. */
  45. def getPairsEqualingToSumSet(): Set[(Int, Int)] = {
  46. val setOfPairs = new HashSet[(Int, Int)]()
  47. val map: Map[Int, ListBuffer[Int]] = new HashMap[Int, ListBuffer[Int]]()
  48. a.indices.foreach(i => {
  49. val x = -(a(i) - n)
  50. val m = map get x
  51. if (m == None) {
  52. /** put a new List into the value of map **/
  53. map += (x -> ListBuffer(i))
  54. } else {
  55. /** get the list out and update it **/
  56. val mi = m.get
  57. mi += (i)
  58. }
  59. val f = map get a(i)
  60. if (f != None) {
  61. val lb = f.get
  62. setOfPairs += ((a(i), a(f.get.apply(f.get.size - 1))))
  63. }
  64. })
  65. setOfPairs
  66. }
  67. }
  68.  
  69. object PairsSummingToN {
  70.  
  71. def getPairs(tyP: Boolean)(a: Array[Int], n: Int) = {
  72. val solutionSet = new PairsSummingToN(a, n)
  73. tyP match {
  74. case true => solutionSet.getPairsEqualingToSumList()
  75. case false => solutionSet.getPairsEqualingToSumSet()
  76. }
  77. }
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement