Problem Link:
Clash Wildcard 2022
Practice
Problem:
We are given two integers L and R, our task is to find the size of the largest possible group for the range [L, L+1, …. R-1, R]. A group is collection of integers having same friendship value. Friendship value of a number is defined as the floor value of sum of all factors of a number divided by the
number of factors.
Approach:
One of the approach for the given question is to use brute force.
Loop through each element from the range [L, L+1,… R]. Calculate friendship value for each of the element and store the size of largest group formed by elements having same friendship value. Calculate friendship value by taking the floor of sum of all divisors of the number divided by number of divisors.
Setter's Solution (C++)
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int divSum(int n)
{int count=0;
if(n == 1)
return 1;
// Sum of divisors
int result = 0;
// find all divisors which divides 'num'
for (int i = 2; i <= sqrt(n); i++)
{
// if 'i' is divisor of 'n'
if (n % i == 0)
{
// if both divisors are same
// then add it once else add
// both
if (i == (n / i))
{result += i;count++;}
else
{result += (i + n/i);count+=2;}
}
}
// Add 1 and n to result as above loop
// considers proper divisors greater
// than 1.
return (result + n + 1)/(count+2);
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tc;cin>>tc;
while(tc--)
{ map<int,int> dict;
int l,r;
cin>>l>>r;int mx=0;
for(int i=l;i<=r;i++)
{
int dv=divSum(i);
dict[dv]++;
mx=max(mx,dict[dv]);
}
cout<<mx<<"\n";
}
return 0;
}