Algorithm
Problem link- https://www.spoj.com/problems/LCPC12F/
LCPC12F - Johnny The Gambler
Johnny is a gambling addict. He entered a casino and started playing a game with the dealer. The game is as follows: the dealer deals a sequence of N cards, each card containing a number C[i] and asks Johnny how many pairs (j, k) such that j < k and C[j] + C[k] = X. If Johnny answers correctly he wins, otherwise the dealer wins.
Input
The first line of input contains an integer T, the number of test cases. T test cases follow, Each test case start with the value of 0 ≤ X ≤ 2*103 followed by the number of cards 0 < N ≤ 105 followed by N numbers representing the numbers on the cards 0 ≤ C[i] ≤ 103.
Output
There should be T lines, containing the following format.
k. S
Where k is the test case number (starting at 1), a single period, a single space and S representing the number of valid pairs (j, k) as described above.
Sample
Input 1 10 3 1 5 9 Output 1. 1
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
T = int(input())
for case in range(T):
data = list(map(int, input().split()))
X, N = data[0], data[1]
result = 0
counts = [0] * (X + 1)
for i in data[2:]:
if i <= X:
result += counts[X - i]
counts[i] += 1
print('%d. %d' %(case + 1, result))Input
10 3 1 5 9
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int C[1003], arr[100005];
int main()
{
int t,x,n,a;
scanf("%d",&t);
for(int cs=1; cs<=t; cs++){
scanf("%d%d",&x,&n);
memset(C, 0, sizeof C);
for(int i=1; i<=n; i++){
scanf("%d",&a);
C[a]++;
arr[i] = a;
}
long long ans = 0;
for(int i=1; i<=n; i++){
C[arr[i]]--;
int need = x - arr[i];
if(need>=0 && need<=1000){
ans+=C[need];
}
}
printf("%d. %lld\n", cs, ans);
}
}Input
10 3 1 5 9
Output
Demonstration
SPOJ Solution-Johnny The Gambler-Solution in C, C++, Java, Python