Home > Umum > Handshake

Handshake

Problem Statement

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of Board of Directors of Acme.

Output Format

Print the number of handshakes for each test-case in a new line.

Constraints

1 <= T <= 1000
0 < N < 106

This problem is about combinations. The formula is

For factorial calculation I’m using recursive with memoization to optimization process.

Java Solution:

import java.math.BigInteger;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Handshake {

 static Map<Integer, BigInteger> memo = new TreeMap<Integer, BigInteger>();

 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 int a = in.nextInt();
 int[] input = new int[a];
 for(int b = 0; b < a; b++) {
 input[b] = in.nextInt();
 }
 for(int b = 0; b < a; b++) {
 System.out.println(getHanshakePairs(input[b]));
 }
 }

 // calculate combinations
 private static BigInteger getHanshakePairs(int n) {
 return getFactorial(n).divide(getFactorial(n-2).multiply(BigInteger.valueOf(2)));
 }

 // calculate factorial using recursive and memoization 
 private static BigInteger getFactorial(int n) {
 if (n <= 1)
 return BigInteger.ONE;
 if (memo.get(n) == null)
 {
 memo.put(n, BigInteger.valueOf(n).multiply(getFactorial(n-1)));
 }
 return memo.get(n);

 }

}

Output:

handshake

Reference:

https://www.hackerrank.com/challenges/handshake

http://www.mathsisfun.com/combinatorics/combinations-permutations.html

http://en.wikipedia.org/wiki/Memoization

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: