CodeChef: Practical coding for everyone my solution

CodeChef: Practical coding for everyone question

Not sure where to start with this one:

```
[simon@simon-laptop][15:48:59]
[~/tmp/DONTSYNC/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling shoyam-AVERAGE.cpp
+ g++ -std=c++14 shoyam-AVERAGE.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
+ set +x
Successful
[simon@simon-laptop][15:49:03]
[~/tmp/DONTSYNC/hackerrank/otherpeoples]>cat failed_test_case.txt
15
28
28
23
15
16
53
53
19
4
30
31
28
22
52
20
[simon@simon-laptop][15:49:05]
[~/tmp/DONTSYNC/hackerrank/otherpeoples]>cat failed_test_case.txt | ./a.out
shoyam-AVERAGE.cpp:8:26: runtime error: signed integer overflow: 13 * 479001600 cannot be represented in type 'int'
shoyam-AVERAGE.cpp:23:30: runtime error: signed integer overflow: 1932053504 * 2 cannot be represented in type 'int'
shoyam-AVERAGE.cpp:8:26: runtime error: signed integer overflow: 13 * 479001600 cannot be represented in type 'int'
shoyam-AVERAGE.cpp:8:26: runtime error: signed integer overflow: 14 * 1932053504 cannot be represented in type 'int'
shoyam-AVERAGE.cpp:8:26: runtime error: signed integer overflow: 15 * 1278945280 cannot be represented in type 'int'
shoyam-AVERAGE.cpp:25:14: runtime error: variable length array bound evaluates to non-positive value -4
21
```

First things first - there’s no need to use factorials in this

1 Like

I think factorial is neccessary for finding the no of combination of t numbers where any 2 are added.

```
#include <iostream>
using namespace std;
int fac(int n){
if(n==1){ // Check if n == 0 too.
return 1;
}else{
return(n*fac(n-1));
}
}
int s=0;
int main() {
int n;
cin>>n;
float r[n];
for(int i=0 ; i<n ;i++){
cin>>r[i];
}
int t= (fac(n))/(fac(n-2)*2); // Because n-2 can be -1
float a[t];
for(int i=0 ; i<n ;i++){
for(int j=i+1;j<n;j++){
a[s]= (r[i]+r[j])/2;
if(s==t-1){
break;
}else{
s++;
}
}
}
int s=0;
for(int i=0 ; i<n ;i++){
for(int j=0;j<n;j++){
if(a[i]==r[j]){
s++;
}
}
}
cout<<s<<endl;
return 0;
}
```

This is your code. I added two comments, look at them. And as said by @ssjgz , no need to calculate factorials. You can use two pointers and binary search with an overall time complexity of O(N\log{N}).

```
int t = (fac(n))/fac(n-2)*2);
// Can be re-written as
int t = (n * (n - 1)) / 2;
```

1 Like

Try submitting it in C++17