Join Us
can you pls provide me with the mathematical approach you took to conclude this code
Entering edit mode
for question 1
void solve()
{
int n,x;
cin>>n>>x;
int ar[n];
f(i,n)
cin>>ar[i];Q
sort(ar,ar+n);
int ans=0;
for(int i=0;i<n;i++)
{
if(2*ar[i]==x)
ans+=i;
}
cout<<ans<<endl;
}
int32_t main()
{
solve();
}
Entering edit mode
1
To remove the complexity caused by mod I sorted the array and that is right because we are asked to count unordered pairs so sorting will not change the ans no question became ai-aj+ai+aj=p ==>2*ai=p
Entering edit mode
According to me, this would be a solution :
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> arr = {1 , -1 , 2 , -2 , 3 , -3 , 4 , -4};
int sum = 3;
if(sum % 2){
return 0;
}
int count = 0;
int num = 0;
for(int i = 0 ; i < n ; ++i){
if(abs(arr[i]) == sum/2){
count++;
}
else if(abs(arr[i]) < sum/2){
num++;
}
}
int ans = count*num + (count * (count - 1))/2 ;
cout<<ans<<endl;
return 0;
}First of all, if the sum is odd, then we can never find an integer = sum/2 in the array. Hence, No pair exists.
Here, count*num represents the value(sum / 2) pairing up with all the numbers less than sum/2 which is "num".
And (count*(count - 1))/2 are the pairs of sum/2 with sum/2 i.e. if arr[i] == arr[j] == sum/2.
Entering edit mode
Question 1
class Solution {
public void groupSizes(int n, int[] from, int[] to, int[] queries) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n+1; i++) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < from.length; i++) {
adj.get(from[i]).add(to[i]);
adj.get(to[i]).add(from[i]);
}
int[] colors = new int[n+1];
Map<Integer, Integer> colorToSize = new HashMap<>();
int color = 1;
for (int i = 1; i <= n; i++) {
if (colors[i] != 0) continue;
int size = dfs(i, adj, colors, color);
colorToSize.put(color, size);
color++;
}
for (int query : queries) {
System.out.println(colorToSize.get(colors[query]));
}
}
private int dfs(int i, List<List<Integer>> adj, int[] colors, int color) {
colors[i] = color;
int size = 1;
for (int next : adj.get(i)) {
if (colors[next] != 0) continue;
size += dfs(next, adj, colors, color);
}
return size;
}
}
Loading Similar Posts
according to me, this would be a solution :
First of all, if the sum is odd, then we can never find an integer = sum/2 in the array. Hence, No pair exists.
Here, count*num represents the value(sum / 2) pairing up with all the numbers less than sum/2 which is "num".
And (count*(count - 1))/2 are the pairs of sum/2 with sum/2 i.e. if arr[i] == arr[j] == sum/2.