finding the number of pairs of numbers in an array that add up to a number

Question

I am trying to come up with a program that will search inside of an array that is given a length by the user that picks out whether there is a pair of numbers that sum to 7. The idea is that if there is k amount of dice being thrown, how many pairs of numbers out of those dice thrown add up to 7. So far this is all that I could come up with but I am very stuck.

This is the driver class for the program. I have to write a class that will make this driver function properly.

import java.util.Scanner;   
public class SevenDriver{       
   public static void main(String[] args){      
      System.out.println("Enter number of dice to toss");     
      Scanner s = new Scanner(System.in);      
      int diceCount = s.nextInt(); 
      SevenTally t = new SevenTally(diceCount);
      int experiments = 1000000;
      int wins = 0;
      for(int j = 0; j < experiments; j++)
         if(t.experiment()) wins++;
     System.out.println((double)wins/experiments);

   } 
}   

This is what I have so far. It does not currently work or compile. I am just looking for some ideas to get me going. Thanks!

public class SevenTally{
   private int diceCount;

   public SevenTally(int die){
      diceCount = die;
}

   public int genDice(){
      return 1 + (int)(Math.random()*6);
   }

   public boolean experiment(){

      boolean[] nums = new boolean[diceCount];
      int ranNum;
      int sum = 7;
      for(int i = 0; i < nums.length; i++){
         ranNum = genDice();
         if (nums[ranNum] == sum){
            return true;
         }
      }

      int left = 0;
      int right = nums.length - 1;
      while(left<right){
      int tempSum = nums[left] + nums[right];
      if(tempSum == 7){
         return true;
      }
      else if(tempSum>7){
         right--;
     }
     return false;
  }

}

Answer 1

First populate your array of length k with random int in [1;6]

The number of possible pairs in an array of length k is the number of 2-combinations in the array, which is (k-1)*k/2 (http://en.wikipedia.org/wiki/Combination)

You can test all the possible pairs (i,j) in your array like so:

int win = 0;
int tally = 7;

for(int i=0; i<k-1; i++){
  for(int j=i+1; j<k; j++){
    if(array[i]+array[j] == tally){
      win++;
    }
  }
}

What this does is that it sets the first element of the pair to be the first element of the array, and sums it with the other elements one after the other.

It pairs array[0] with array[1] to array[k-1] at the first pass of the i for loop, that's k pairs. Then k-1 pairs at second pass, and so on.

You end up with (k)+(k-1)+(k-2)+...+1 pairs, and that's exactly (k-1)*k/2 pairs.

done =]

edit: sorry, haven't read the whole thing. the method experiment() is supposed to return a boolean. you can return win>0?true:false; for example...

Answer 2

This Wiki page has some algorithms to do that. Its not a trivial problem...

Answer 3

You're generating a random number in ranNum, and then using it as an index into the array nums. Meanwhile, nums never gets filled, so no matter which box you index into, it never contains a 7.

What you want to do, if I understand your problem correctly, is fill each space in the array with the result of a die roll, then compare every two positions (rolls) to see if they sum to seven. You can do that using a nested for loop.

Essentially, you want to do this: (written in pseudocode as I'm not a java programmer)

int[] results[numrolls]
for (count = 0 to numrolls-1) { results[numrolls]=dieRoller() }
for (outer = 0 to numrolls-2)
 for (inner = outer+1 to numrolls-1)
  if (results[outer] + results[inner] == 7) return true
return false;

However, in this case there's an even easier way. You know that the only ways to get a sum of 7 on 2d6 are (1,6),(2,5),(3,4),(4,3),(5,2),(6,1). Set up a 6-length boolean array, roll your dice, and after each roll set res[result] to true. Then return (1-based array used for simplicity) ( (res[1] && res[6]) || (res[2] && res[5]) || (res[3] && res[4]) ).

Answer 4

ArrayIndexOutOfBoundsException means you are trying to access an element of the array that hasn't been allocated.

In your code, you create a new array d of length diceCount, but then you genDice() on always 6 elements.