Beautiful Triplets
here a[j]-a[i] must be equal to d and
a[k]-[j] = d
so solving a[j]-a[i] =d we get a[i] = a[j] -d
and solving a[k]-a[j] =d we get a[k] = a[j] + d
so according to problem statement a[j]-d and a[j] +d must be in the array...
but if we write the if condition as h[a[i]-d] >=1 and h[a[i]+d >=1 then this logic will fail wen there are repetitions
Example:
10 3
1 6 7 7 8 10 12 13 14 19
here 10-3 = 7 and 7 exists in array
10+3 is 13 and 13 also exists in array but the if condition will only count once
but since there is another 7, another beautiful triplet (7,10,13) also exists.
No we must change the if condition
a[j]-d, a[j] and a[j]+d must be in array
it is as good as
a[i], a[i]+d, a[i]+2d must exist in array (since a[i] = a[j]-d)
so our for loop would be
h[a[i]+d] >=1 and h[a[i]+2*d] >=1
Solution:
#include <stdio.h>
int main()
{
int n,d;
scanf("%d%d", &n,&d);
long long int a[n],h[2000001]={0},c=0,i;
for (i = 0; i < n; i++)
{
scanf("%lld",&a[i]);
h[a[i]]++;
}
for( i=0;i<n;i++)
if( h[a[i]+d] >=1 && h[a[i]+2*d]>=1)
c++;
printf("%lld\n", c);
}
Equalize the Array
https://www.hackerrank.com/challenges/equality-in-a-array/problem
#include <stdio.h>
int main()
{
int n,h[101]={0};
scanf("%d", &n);
int a[n],max=0,c=0;
for(int i=0;i<n;i++)
{
scanf("%d", &a[i]);
h[a[i]]++;
if(h[a[i]]>max)
max=h[a[i]];
}
printf("%d",n-max);
}
Sock Merchant
https://www.hackerrank.com/challenges/sock-merchant/copy-from/62004605
In C :
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main() {
int n,i,s=0;
scanf("%i", &n);
int *ar = malloc(sizeof(int) * n);
int b[101]={0};
for(int ar_i = 0; ar_i < n; ar_i++){
scanf("%i",&ar[ar_i]);
b[ar[ar_i]]++;
}
for(i=0;i<101;i++)
s=s+b[i]/2;
printf("%d\n", s);
return 0;
}
In C++
int main() {
map<int,int> socks;
int i, total=0;
cin.ignore();
while(cin>>i){
socks[i]++;
if(!(socks[i]%2))
total++;
}
cout<<total;
return 0;
}
In Java
static int sockMerchant(int n , int ar[])
{
Map<Integer, Integer> map = new HashMap();
int ans=0;
for(int val: ar)
{
Integer c = map.get(val);
if(c == null)
map.put(val,1);
else
map.put(val,c+1);
}
for(int z: map.values())
ans=ans+z/2;
return ans;
}
========================================================================
https://www.hackerrank.com/challenges/beautiful-triplets/problem
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int h[20001]={0};
int beautifulTriplets(int d, int arr_size, int* arr) {
// Complete this function
int c=0;
for(int i=1;i<arr_size;i++)
if(h[arr[i]-d] ==1 && h[arr[i]+d]==1)
c++;
return c;
}
int main() {
int n;
int d;
scanf("%i %i", &n, &d);
int *arr = malloc(sizeof(int) * n);
for (int arr_i = 0; arr_i < n; arr_i++) {
scanf("%i",&arr[arr_i]);
h[arr[arr_i]]++;
}
int result = beautifulTriplets(d, n, arr);
printf("%d\n", result);
return 0;
}
========================================================================
Weapon Value CodeChef solution
#include<stdio.h>
int main() {
int t;
scanf("%d",&t);
while(t--)
{
int n,i,j,c=0;
scanf("%d",&n);
char st[n][11];
int h[26]={0};
for(i=0;i<n;i++)
scanf("%s",&st[i]);
for(i=0;i<n;i++)
{
for(j=0;st[i][j]!='\0';j++)
{
if(st[i][j] == '1')
h[j]++;
}
}
for(i=0;i<11;i++)
if(h[i] !=0 && h[i]%2 == 1)
c++;
printf("%d\n",c);
}
}
Other Wonderful problems on hashing
