I came across the below problem in a coding challenge: Let's define 2 functions a function F(i), \$F(i)\$ and Val(i\$Val(i,j)\$,j) for an Array Aarray \$A\$ of size N\$N\$ as follows:
F(i) = ∑ Val(i,j), for j = i+1 to N
Val(i,j)=1 ,if A[i]<A[j], otherwise Val(i,j)= 0.
I$$ \begin{align} F(i) =& \sum_{j=i+1}^{N} Val(i,j) \\ \\ Val(i, j) =& \begin{cases} 1,\qquad & \textrm{if } A[i] < A[j] \\ 0,\qquad & \textrm{otherwise} \end{cases} \end{align} $$ I need to find the number of distinct unordered pairs of elements (a,b) in array A\$A\$, such that F(a)+F(b)≥K\$F(a)+F(b) \ge K\$.
I came across the below problem in a coding challenge: Let's define 2 functions a function F(i) and Val(i,j) for an Array A of size N as follows:
F(i) = ∑ Val(i,j), for j = i+1 to N
Val(i,j)=1 ,if A[i]<A[j], otherwise Val(i,j)= 0.
I need to find the number of distinct unordered pairs of elements (a,b) in array A, such that F(a)+F(b)≥K
I came across the below problem in a coding challenge: Let's define 2 functions, \$F(i)\$ and \$Val(i,j)\$, for an array \$A\$ of size \$N\$ as follows:
$$ \begin{align} F(i) =& \sum_{j=i+1}^{N} Val(i,j) \\ \\ Val(i, j) =& \begin{cases} 1,\qquad & \textrm{if } A[i] < A[j] \\ 0,\qquad & \textrm{otherwise} \end{cases} \end{align} $$ I need to find the number of distinct unordered pairs of elements (a,b) in array \$A\$, such that \$F(a)+F(b) \ge K\$.
Distinct unordered pairs of an array which satisfy a condition
I came across the below problem in a coding challenge: Let's define 2 functions a function F(i) and Val(i,j) for an Array A of size N as follows:
F(i) = ∑ Val(i,j), for j = i+1 to N
Val(i,j)=1 ,if A[i]<A[j], otherwise Val(i,j)= 0.
I need to find the number of distinct unordered pairs of elements (a,b) in array A, such that F(a)+F(b)≥K
Here is my solution:
#include<iostream>
#include<cassert>
#define max 1000000000
int main()
{
unsigned int N, K;
std::cin >> N;
assert((1 <= N) && (N <= 1000000));
std::cin >> K;
assert((0 <= K) && (K <= max));
unsigned int a[N], F[N];
for(unsigned int i = 0; i < N; i++)
{
std::cin >> a[i];
assert((1 <= a[i]) && (a[i] <= max));
}
int sum = 0, val = 0;
for(unsigned int i = 0; i < N; i++)
{
for(unsigned int j = i+1; j < N; j++)
{
if(a[i] < a[j])
val = 1;
else
val = 0;
sum = sum + val;
}
F[i] = sum;
sum = 0;
}
int count = 0;
for(unsigned int i = 0; i < N; i++)
{
for(unsigned int j = i+1; j < N; j++)
{
if(F[i] + F[j] >= K)
count++;
}
}
std::cout << count << std::endl;
}
While this works, I would want to know if there is a way to write optimized code which works fast even for larger inputs.