We have to make $$$A$$$ equal to $$$B$$$ by adding $$$x$$$ any number of time.

We initially have $$$Rs$$$ $$$A$$$ and we have to achieve amount $$$Rs$$$ $$$B$$$ by adding only $$$Rs$$$ $$$x$$$ any number of time .

If we assume $$$k$$$ is number of notes required . We just have to solve the equation $$$A$$$$$$+$$$$$$k$$$$$$x$$$$$$=$$$$$$B$$$.

The solution exists if $$$B$$$$$$-$$$$$$A$$$ is divisible by $$$x$$$ and the answer will be $$$B$$$$$$-$$$$$$A$$$ divided by $$$x$$$ else $$$-1$$$.

shinigami_09

#include <bits/stdc++.h>
 
using namespace std;
 typedef long long int ll;
 
void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
 
int main(){
    fastIO();
   
    ll t;
    cin>>t;
    while(t--){
        ll a,b,x;
        cin>>a>>b>>x;
        if((b-a)%x==0 && b>=a){
            cout<<(b-a)/x<<endl;
        }
        else cout<<-1<<endl;
       
    }
       
    return 0;
}

momotaroUWU

a, b, x = map(int, input().split())
if((b - a) % x == 0):
   print((b - a) // x)
else:
   print(-1)

Prerequisites: 2-d array.

The idea behind this problem is pretty simple, Iterate through the 2-d array from the top-left corner ie. $$$1$$$st row and $$$1$$$st column, and find out if there are $$$k$$$ consecutive unoccupied rooms on the current row. If rooms are found, replace them with \t{'F'} otherwise print no. As the higher floored rooms are preferred, the normal iteration would give the optimal results.

k_rishabh

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define yes cout << "YES\n" 
#define no cout << "NO\n" 
#define all(x) (x).begin(),(x).end()

const ll MOD = 1e9 + 7;
const ll INF = 1e9;

void solve(){
    //inputs
    ll n , m , k ; cin >> n >> m >> k ;
    vector<string> v ;
    string req;
    for(int i = 0 ; i < k ; i++){
        req.pb('O');
    }

    for(int i = 0 ; i < n ; i++){
        string s ; cin >> s ;
        v.pb(s);
    }

    //iterating through the matrix : 
    for(auto &x : v){
        string t = x ;
        for(int i = 0 ; i <= m-k ; i++){
            if(t.substr(i,k) == req){ //required condition
                yes;
                ll yo = i;
                while(k--){
                    x[yo] = 'F'; //replacing with F
                    yo++;
                }
                for(auto x : v){
                    cout << x << endl;
                }
                return;
            }
        }
    }
    no;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tc = 1;
    // cin >> tc;
    while(tc--)
    {
        cout << setprecision(15) << fixed ;
        solve();
        cout << endl;
    }

}

momotaroUWU

n, m, k = map(int, input().split())
a = ["" for i in range(n)]
for i in range(n):
    a[i] = list(input())
# print(a)
flag = False
row = -1
for i in range(n):
    cur, cnt = -1, 0
    for j in range(m):
        if(a[i][j] == "O" and cur == -1):
            cur = j
            cnt = 1
        elif(a[i][j] == "O"):
            cnt += 1
        else:
            cur = -1
            cnt = 0
        if(cnt == k):
            row = i
            flag = True
            break
    if(flag):
        break

if(flag):
    for i in range(k):
        a[row][cur + i ] = 'F'
    print("YES")
    for i in a:
        print(''.join(i))
else:
    print("NO")

As we need to construct set's of the form $$$1$$$ to $$$k$$$. We can solve this problem by storing frequencies of the baggage's.

Think about the maximum size of the set you can construct given the number of baggage's is $$$n$$$ ($$$1$$$ $$$≤$$$ $$$n$$$ $$$≤$$$ $$$10^5$$$).

For minimizing the baggage's to be carried, we need to maximize the size of each set of baggage's.

The idea behind the solution is to store the frequencies of all the baggage's which have value $$$≤$$$ $$$10^5$$$ because the maximum number of baggage's we can have is $$$10^5$$$. For minimizing the baggage's to be carried, we need to maximize the size of each set of baggage's. For maximizing size of each set, we start constructing set's of maximum possible size and reducing their frequencies after each set. For keeping track of number of baggage's for all set's, we add the size of each set in a $$$cnt$$$ variable. We do this until the frequency of value $$$1$$$ becomes $$$0$$$ because $$$1$$$ is the first baggage for every set. We cannot construct more set's if there is no $$$1$$$ available.

So the minimum number baggage's to be carried by $$$Rishabh$$$ is $$$n$$$ $$$-$$$ $$$cnt$$$.

Overall Complexity : $$$O(n)$$$ or $$$O(nlogn)$$$ (for map) for each testcase

monkedluffy

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;
 
int main() {
    
    ll t ;
    cin >> t ;
    while (t--)
    {
        ll n , cnt = 0 ;
        cin >> n ;
        ll a[100002] = {0} ;
        for(ll i = 0 ; i < n ; i++)
        {
            ll x ;
            cin >> x ;
            if(x <= 100000)
                a[x]++ ;
        }
        
        while(a[1] != 0){
            cnt++ ;
            a[1]-- ;
            ll x = 2 ;
            while(a[x] != 0){
                cnt++ ;
                a[x]-- ;
                x++ ;
            }
        }
        
        cout << n - cnt << endl ;
    }
    return 0;
}

k_rishabh

#include <bits/stdc++.h>
using namespace std ;
using namespace std::chrono;

#define ll long long 
#define pb push_back 
#define yes cout << "YES" 
#define no cout << "NO" 
#define all(x) (x).begin(),(x).end()

const long long int mod = 1e9 + 7 ;
const long long int INF = 1e18 ;

void readvec(vector<ll> &v){
    for(int i = 0 ; i < v.size() ; i++){
        cin >> v[i] ;
    }
}

void printvec(vector<ll> &v){
    for(int i = 0 ; i < v.size() ; i++){
        cout << v[i] << " ";
    }
}

//For debugging :
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(long long t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(long double t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(unsigned long long t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

//binary exponentiation 
long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

void solve(){
    ll n ; cin >> n ;
    vector<ll> v(n); readvec(v);
    map<ll,ll> m ;
    for(auto x : v){
        m[x]++;
    }
    ll a = INF , maxi = *max_element(all(v));
    for(int i = 1 ; i <= maxi ; i++){
        if(m[i] == 0){
            a = i ;
            break;
        }
    }
    debug(a)

    if(a == INF){
        a = maxi;
    }

    debug(a)
    debug(m)

    ll ans = 0 ;
    while(m[1] > 0){
        debug(m)
        ll yo = 1 ;
        while(m[yo] > 0){
            ans++;
            m[yo]--;
            yo++;
        }

    }

    cout << n - ans;
}

int main(){
    auto start = high_resolution_clock::now();
    ios::sync_with_stdio(false);
    cin.tie(0);

#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
 
    int tests = 1 , test_case = 1;
    cin >> tests ;
    while(tests--){
        cout << setprecision(15) << fixed ;
        solve() ;
        cout << '\n' ;
        // cout << "Case #" << test_case << ": " << ans << '\n' ;
    }

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cerr << "\n\nTime taken : " << fixed << duration.count() / 1000000.0 << "seconds" << "\n";
}

momotaroUWU

from collections import defaultdict
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    mp = defaultdict(int)
    for i in a:
        mp[i] += 1
    
    if(mp[1] == 0):
        print(n)
    else:
        cur = -1
        prev = -1
        good = 0
        for k, v in mp.items():
            if(prev == -1):
                prev = k
                cur = v
                good += cur
            else:
                if(k != prev + 1):
                    break
                else:
                    prev = k
                    cur = min(v, cur)
                    good += cur
        print(n - good)

Handle the corner cases for $$$a$$$ $$$ \gt $$$ $$$b$$$ and $$$a$$$ $$$=$$$ $$$b$$$.

Make two different cases for $$$even$$$ and $$$odd$$$ values of $$$a$$$.

On seeing the constraints on $$$a$$$ ($$$1$$$ $$$≤$$$ $$$a$$$ $$$≤$$$ $$$10^6$$$), $$$b$$$ ($$$1$$$ $$$≤$$$ $$$b$$$ $$$≤$$$ $$$10^{12}$$$) and following the pattern given operations will follow, we can say that the number of operations will never exceed $$$10^6$$$. So we can apply binary search to find the number of operations needed to make $$$a$$$ $$$=$$$ $$$b$$$.

If $$$a$$$ is even, then we can only apply the first operation on it because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. After following the pattern, we get that till $$$n^{th}$$$ operation we add $$$n(n+1)$$$ to $$$a$$$. Now we can easily apply binary search, to find the $$$n^{th}$$$ operation after which $$$a$$$ $$$=$$$ $$$b$$$. If the binary search gives no result, then the answer is $$$NO$$$ cause $$$n$$$ must be an integer, otherwise the answer is $$$YES$$$ and the number of operations is $$$n$$$.

If a is odd, then first we have to apply the second operation which adds $$$2i-1$$$ (an odd number) to $$$a$$$ making $$$a$$$ an even number. After this operation we can only apply the first operation on $$$a$$$ because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. Now we have already applied one operation, so $$$i$$$ starts from $$$2$$$ for next operation. After following the pattern, we get that till $$$n^{th}$$$ operation we add $$$n(n+1)-2$$$ to $$$a$$$. Now we can easily apply binary search, to find the $$$n^{th}$$$ operation after which $$$a$$$ $$$=$$$ $$$b$$$. If the binary search gives no result, then the answer is $$$NO$$$ cause $$$n$$$ must be an integer, otherwise the answer is $$$YES$$$ and the number of operations is $$$n+1$$$.

Overall Complexity : $$$O(logn)$$$ for each testcase

Yoks1729-

#include<bits/stdc++.h>
using namespace std;

void solve()
{
    long long int a,b;
    cin>>a>>b;
    if(a==b)
    {
        cout<<"YES"<<'\n'<<0<<'\n';return;
    }
    if(a%2==0)
    {
        long long int s=0,e=1000000,ans=-1;
        while(s<=e)
        {
            long long int mid=s+(e-s)/2;
            long long int here=a+mid*(mid+1);
            if(here>b)e=mid-1;
            else if(here<b)s=mid+1;
            else {ans=mid;break;}
        }
        if(ans==-1)
        {
            cout<<"NO"<<'\n';return;
        }
        cout<<"YES"<<'\n'<<ans<<'\n';return;
    }
    a++;
    long long int s=0,e=1000000,ans=-1;
    b+=2;
    while(s<=e)
    {
        long long int mid=s+(e-s)/2;
        long long int here=a+mid*(mid+1);
        if(here>b)e=mid-1;
        else if(here<b)s=mid+1;
        else {ans=mid;break;}        
    }
    if(ans==-1)
    {
        cout<<"NO"<<endl;return;
    }
    cout<<"YES"<<'\n';
    cout<<ans<<'\n';
}

int main()
{
    int tc=1;
    cin>>tc;
    while(tc--)
    {
        solve();
    }
}

momotaroUWU

def solve():
    a, b = map(int, input().split())
    if(a == b):
        print("YES")
        print(0)
    elif(a % 2 == 0):
        l , r = -1, 1000000
        while(r - l > 1):
            m = (l + r)//2
            if(a + m*(m+1) >= b):
                r = m
                if(a + m*(m+1) == b):
                    print("YES")
                    print(m)
                    return
            else:
                l = m
        print("NO")
    else:
        a -= 1
        l , r = -1, 1000000
        while(r - l > 1):
            m = (l + r)//2
            if(a + m*(m+1) >= b):
                r = m
                if(a + m*(m+1) == b):
                    print("YES")
                    print(m)
                    return
            else:
                l = m
        print("NO")

for _ in range(int(input())):
    solve()

The idea behind the solution is to divide them in two cases for $$$even$$$ and $$$odd$$$ values of $$$a$$$.

If a is even, then we can only apply the first operation on it because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. Let us assume that after the $$$n^{th}$$$ operation, a becomes equal to b then if we follow the pattern after every operation we get the following equation $$$a$$$ $$$+$$$ $$$n(n+1)$$$ $$$=$$$ $$$b$$$. If we solve the following equation for n, we get two values for $$$n$$$ one positive and one negative. But as $$$n$$$ cannot be negative, we choose the positive value. Also n should be an integer (we cannot apply half of an operation), if n is an integer then answer is $$$YES$$$ and the number operation's applied is $$$n$$$. But if $$$n$$$ is not an integer, there is no possible integer value of $$$n$$$ for which $$$a$$$ $$$=$$$ $$$b$$$ and the answer is $$$NO$$$.

If a is odd, then first we have to apply the second operation which adds $$$2i-1$$$ (an odd number) to $$$a$$$ making $$$a$$$ an even number. After this operation we can only apply the first operation on $$$a$$$ because after every operation we add $$$2i$$$ which is an even number and addition of two even numbers is an even number. Let us assume that after the $$$n^{th}$$$ operation, a becomes equal to b then if we follow the pattern after every operation we get the following equation $$$a$$$ $$$+$$$ $$$n(n+1)$$$ $$$-$$$ $$$1$$$ $$$=$$$ $$$b$$$. If we solve the following equation for n, we get two values for $$$n$$$ one positive and one negative. But as $$$n$$$ cannot be negative, we choose the positive value. Also n should be an integer (we cannot apply half of an operation), if n is an integer then answer is $$$YES$$$ and the number operation's applied is $$$n$$$. But if $$$n$$$ is not an integer, there is no possible integer value of $$$n$$$ for which $$$a$$$ $$$=$$$ $$$b$$$ and the answer is $$$NO$$$.

Overall Complexity : $$$O(logn)$$$ (complexity of sqrt() function) for each testcase

monkedluffy

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;
 
int main() {
    
    ll t ;
    cin >> t ;
    while (t--)
    {
        ll a , b ;
        cin >> a >> b ;
        
        if(a > b)
        {
            cout << "NO" ;
        }
        else if(a == b)
        {
            cout << "YES" << endl ;
            cout << 0 ;
        }
        else
        {
            ll x = b - a ;
            if(a%2 == 0)
            {
                ll n = (sqrt(4*x + 1) - 1)/2 ;
                
                if(n*(n+1) == x)
                {
                    cout << "YES" << endl ;
                    cout << n ;
                }
                else
                {
                    cout << "NO" ;
                }
            }
            else
            {
                ll n = (sqrt(4*x + 5) - 1)/2 ;
                
                if(n*(n+1) == x + 1)
                {
                    cout << "YES" << endl ;
                    cout << n ;
                }
                else
                {
                    cout << "NO" ;
                }
            }
        }
        cout << endl ;
    }
    return 0;
}

momotaroUWU

from math import sqrt
for _ in range(int(input())):
    a, b = map(int, input().split())
    if(a > b):
        print("NO")
    elif (a == b):
        print("YES")
        print(0)
    elif (a % 2 == 0):
        n = int(((sqrt(4*(b-a) + 1) - 1)/2))
        if(n*(n+1) == b - a):
            print("YES")
            print(n)
        else:
            print("NO")
    else:
        a -= 1
        n = int(((sqrt(4*(b-a) + 1) - 1)/2))
        if(n*(n+1) == b - a):
            print("YES")
            print(n)
        else:
            print("NO")

Frequencies of all the elements in the array are enough to solve the problem.

For a subsequence of equal elements to have $$$XOR$$$ equal to $$$0$$$, the length of the subsequence should be even. So, the number of even length subsequences has to be calculated for all distinct numbers.

Number of even length subsequences from $$$n$$$ elements $$$=$$$ $$$2^{(n-1)}$$$.

Consider the edge case ($$$a_{i}$$$ $$$=$$$ $$$0$$$) and integer overflows.

Prerequisites: Properties of $$$XOR$$$, Maps.

For the $$$XOR$$$ of all the numbers in the subsequence with equal elements to be equal to $$$0$$$, it should have an even number of elements because $$$A$$$ XOR $$$A$$$ = $$$0$$$, therefore all the pairs would cancel each other up. But if the subsequence contains $$$0$$$ only, then odd length subsequences would also be feasible. So, the final goal is to calculate the number of even lengthed subsequences for all numbers other than $$$0$$$ and the number of subsequences containing $$$0$$$.

Let $$$n$$$ be the frequency of a non-zero element, then the number of even lengthed subsequences is $$$2^{n-1}$$$ $$$-$$$ $$$1$$$ and if the number of zeroes $$$=$$$ $$$n$$$, then the number of feasible subsequences are $$$2^{n}$$$ $$$-$$$ $$$1$$$

k_rishabh

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define yes cout << "YES" 
#define no cout << "NO" 
#define all(x) (x).begin(),(x).end()

const ll mod = 1e9 + 7;
const ll INF = 1e9;

long long int power(long long int n, long long int b){
    long long int ans = 1 ;
    for(int i = 0 ; i < b ; i++){
        ans = (ans*n)%mod;
    }
    return ans%mod;
}
 
void solve(){
    ll n ; cin >> n ;
    map<ll,ll> m ;
    for(int i = 0 ; i < n ; i++){
        ll x ; cin >> x ;
        m[x]++;
    }
    ll s = m.size();

    ll count = 0 , zeroes = (power(2, m[0])) % mod - 1;
    for(auto x : m){
        if(x.first == 0){
            continue;
        }
        count += (power(2, x.second-1))%mod - 1;
        count %= mod;
    }
    cout << (count + zeroes%mod)%mod ;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tc = 1;
    cin >> tc;
    while(tc--)
    {
        cout << setprecision(15) << fixed ;
        solve();
        cout << endl;
    }

}

momotaroUWU

from collections import defaultdict

def binpow(x, y, p) :
    res = 1     # Initialize result
 
    # Update x if it is more
    # than or equal to p
    x = x % p
     
    if (x == 0) :
        return 0
 
    while (y > 0) :
         
        # If y is odd, multiply
        # x with result
        if ((y & 1) == 1) :
            res = (res * x) % p
 
        # y must be even now
        y = y >> 1      # y = y/2
        x = (x * x) % p
         
    return res

mod97 = 1000000007

for _ in range(int(input())):
    # Input
    n = int(input())
    a = list(map(int, input().split()))
    
    # To Store Frequency
    dt = defaultdict(int)
    
    for i in range(n):
        dt[a[i]] += 1
    
    ans = 0
    
    for k in dt.keys():
        v = dt[k]
        if(k == 0):
            ans = (ans + binpow(2, v, mod97) - 1)%mod97 
        else:
            ans = (ans + binpow(2, v-1, mod97) - 1)%mod97
    
    print(ans)

Carefully see the constraints on $$$t$$$ ($$$1$$$ $$$≤$$$ $$$t$$$ $$$≤$$$ $$$10^5$$$) and $$$n$$$ ($$$1$$$ $$$≤$$$ $$$n$$$ $$$≤$$$ $$$10^5$$$).

You can apply brute force for calculating $$$Unique$$$ $$$Numbers$$$ for each value of $$$n$$$.

The idea behind the solution is to pre-compute the number of $$$Unique$$$ $$$Numbers$$$ for each value of $$$n$$$ as constraints are of order $$$10^5$$$. We maintain a $$$cnt$$$ variable which stores number of $$$Unique$$$ $$$Numbers$$$ till given $$$n$$$. Let us start from $$$n$$$ $$$=$$$ $$$1$$$, it is a $$$Unique$$$ $$$Number$$$ increment $$$cnt$$$ by $$$1$$$ and store this value for $$$n$$$ $$$=$$$ $$$1$$$ which is $$$1$$$. Now for $$$n$$$ $$$=$$$ $$$2$$$, it is a $$$Unique$$$ $$$Number$$$ increment $$$cnt$$$ by $$$1$$$ and store this value for $$$n$$$ $$$=$$$ $$$2$$$ which is $$$2$$$. Now perform this for all values of n till $$$10^5$$$.

Now we can tell the number of $$$Unique$$$ $$$Numbers$$$ for any value of $$$n$$$ till $$$10^5$$$ in $$$O(1)$$$.

Overall Complexity : $$$O(N)$$$

monkedluffy

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;
 
int main() {
   
    ll ans[100001] , cnt = 0;
    for(ll i = 1 ; i <= 100000 ;i++)
    {
        set<ll> s ;
        ll temp = i , x = 0;
        while(temp != 0){
            s.insert(temp%10) ;
            temp = temp/10 ;
            x++ ;
        }
       
        if(s.size() == x)
            cnt++ ;
        ans[i] = cnt ;
    }
    
    ll t ;
    cin >> t ;
    while (t--)
    {
        ll n ;
        cin >> n ;
        cout << ans[n] << endl ;
    }
    return 0;
}

momotaroUWU

m = 100000 + 1
cnt = [0 for i in range(m)]

def solve():
    n = int(input())
    print(cnt[n])

cnt[0] = 0
cur = 0
for i in range(1, m):
    s = str(i)
    uniDigits = set(s)
    if(len(uniDigits) == len(s)):
        cur += 1
    cnt[i] = cur

for _ in range(int(input())):
    solve()

monkedluffy

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std ;
typedef long long ll ;
#define endl "\n" ;
long long mod7 = 1000000007 ;
double pi = 3.14159265358979323846 ;


int main() {
   
    ll f[10] ;
    f[0] = 0 ;
    for(ll i = 1 ; i < 10 ; i++){
        ll cnt = 9 , x = 9;
        for(ll j = 1 ; j < i ; j++){
            cnt *= x ;
            x-- ;
        }
        f[i] = cnt + f[i-1] ;
    }
   
    ll t ;
    cin >> t ;
    while (t--)
    {
        ll n , ans = 0 ;
        cin >> n ;
       
        if(n <= 9){
            ans = n ;
        }
        else
        {
            set<ll> s ;
            vector<ll> v ;
            ll temp = n ;
            while(temp!=0){
                v.push_back(temp%10) ;
                temp = temp/10 ;
            }
           
            reverse(v.begin(),v.end()) ;
            
            ans = f[v.size()-1] ;
            
            for(ll i = 0 ; i < v.size() ; i++){
                
                ll x = v[i] , y = 9 - i ;
                if(i == 0)
                    x-- ;
                    
                for(ll j = 0 ; j < i ; j++){
                    if(v[i] > v[j])
                        x-- ;
                }
                
                for(ll j = 1 ; j < v.size()-i ; j++){
                    x *= y ;
                    y-- ;
                }
               
                ans += x ;
                s.insert(v[i]) ;
                
                if(s.size() != i + 1)
                    break ;
            }
            
            // Checking whether n is Unique Number or not
            if(s.size() == v.size()){
                ans++ ;
            }
    
        }
        
        ll cnt = 0 ;
        set<ll> s ;
        while(ans != 0){
            s.insert(ans%10) ;
            cnt++ ;
            ans = ans/10 ;
        }
        
        if(cnt == s.size())
            cout << "YES" ;
        else
            cout << "NO" ;
            
        cout << endl ;
       
    }
    return 0;
}

Prerequisites: Disjoint Set Union and Segment Tree.

The main observation to make about the problem is that we are asked to answer range query and keep the record of different groups in the rooms. As it is evident from the the problem that we are required to make range query with updates and we already know that min function follows associative property therefore is it optimal to use segment tree. As for maintaining the number of groups in different rooms for that we can use disjoint set union data structure with path compression and rank heuristic for best time and space complexity. We need to maintain different disjoint set union for each room.

momotaroUWU

#include<bits/stdc++.h>

using namespace std;

const long long INF = (1e18);

class segtree {
private:
    // Data Members
    long long size;
    vector<long long> tree;
 
    // Encapaclation
    void set(long long i, long long v, long long x, long long lx, long long rx){
        if(rx - lx == 1){
            tree[x] = v;
            return;
        }
        long long m = (lx + rx)/2;
        if(i < m){
            set(i, v, 2*x+1, lx, m);
        } else {
            set(i, v, 2*x+2, m, rx);
        }
 
        tree[x] = min(tree[2*x+1], tree[2*x+2]);
    }
 
    long long op(long long l, long long r, long long x, long long lx, long long rx){
        if(l >= rx or r <= lx){
            return INF;
        }
        if(l <= lx and rx <= r){
            return tree[x];
        }
        long long m = (lx + rx)/2;
        long long s1 = op(l, r, 2*x+1, lx, m);
        long long s2 = op(l, r, 2*x+2, m, rx);
        return min(s1, s2);
    }
 
public:
    // Functions
    void init(long long n){
        size = 1;
        while(size < n) size *= 2;
        tree.assign(2*size, INF);
    }
 
    void set(long long i, long long v){
        set(i, v, 0, 0, size);
    }
 
    long long op(long long l, long long r){
        return op(l, r, 0, 0, size);
    }
};

template<typename T>
class DSU {
public:
	std::vector<T> p;
	std::vector<T> r;
	
	DSU(size_t n){
		p = std::vector<T>(n);
		std::iota(p.begin(), p.end(), 0);
		r = std::vector<T>(n, 1);
	}
 
	T find(T x) {
        if(x > p.size()){
            cerr << "Error element not in array or vector" << endl;
            return LLONG_MIN;
        }
		T y = x;
		while (y != p[y]) {
			y = p[y];
		}
		while (x != p[x]) {
			T z = p[x];
			p[x] = y;
			x = z;
		}
		return y;
	}
 
	void join(T x, T y) {
		x = find(x), y = find(y);
        if(r[x] > r[y]){
            swap(x, y);
        }
		p[x] = y;
		if (r[x] == r[y] and x != y) {
			r[y]++;
		}
	}
};

void solve();

int main(int argc, char const *argv[]){
    // For Fast IO
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    
    // Solution Starts
    solve();
    
    return 0;
}

void solve(){
    long long n, m; cin >> n >> m;
    vector<DSU<long long>> dsu(n, DSU<long long>(m));
    segtree st; st.init(n);

    for(long long i = 0; i < n; i++){
        st.set(i, m);
    }

    long long q; cin >> q;
    while(q--){
        long long c; cin >> c;
        if(c == 1){
            long long sno, x, y;
            cin >> sno >> x >> y;

            // 0 indexcing 
            sno--; x--; y--;

            // Joining
            // O(1)
            long long p_x = dsu[sno].find(x), p_y = dsu[sno].find(y);
            if(p_x != p_y){
                dsu[sno].join(x, y);
                long long val = st.op(sno, sno + 1);
                val--;
                st.set(sno, val);
            }
        } else {
            long long l, r; cin >> l >> r;

            // O indexcing
            l--; r--;

            // Range Query
            // O(log(n))
            cout << st.op(l, r + 1) << "\n";
        }
        // set and which people are in same group
        // minimum numbers of group in [L, R]
    }
}

momotaroUWU

class DSU(object):
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.r = [1 for i in range(n)]
        
    def find(self, x):
        y = x
        while(y != self.p[y]):
            y = self.p[y]
        while(x != self.p[y]):
            z = self.p[x]
            self.p[x] = y
            x = z
        return x
        
    def join(self, x, y):
        x, y = self.find(x), self.find(y)
        if(self.r[x] > self.r[y]):
            x, y = y, x
        self.p[x] = y
        if(self.r[x] == self.r[y] and x != y):
            self.r[y] += 1

INF = float('inf')

class segtree(object):
    def __init__(self, n):
        self.size = 1
        while(self.size < n):
            self.size *= 2
        # self.size *= 2
        self.tree = [INF for i in range(2*self.size)]
        
    def assign(self, i, v):
        self.assignf(i, v, 0, 0, self.size)
    
    def assignf(self, i, v, x, lx, rx):
        if(rx - lx == 1):
            self.tree[x] = v
            return
        m = (lx + rx) // 2
        if(i < m):
            self.assignf(i, v, 2*x + 1, lx, m)
        else:
            self.assignf(i, v, 2*x + 2, m, rx)
        self.tree[x] = min(self.tree[2*x + 1], self.tree[2*x + 2])
    
    def query(self, l, r):
        return self.queryf(l, r, 0, 0, self.size)
        
    def queryf(self, l, r, x, lx, rx):
        if(l >= rx or r <= lx):
            return INF
        if(l <= lx and rx <= r):
            return self.tree[x]
        m = (lx + rx) // 2
        s1 = self.queryf(l, r, 2*x + 1, lx, m)
        s2 = self.queryf(l, r, 2*x + 2, m, rx)
        return min(s1, s2)

def solve():
    n, m = map(int, input().split())
    dsu = [DSU(m) for i in range(n)]
    st = segtree(n)
    for i in range(n):
        st.assign(i, m)

    q = int(input())

    for _ in range(q):
        c = list(map(int, input().split()))

        if(c[0] == 1):
            sno, x, y = c[1], c[2], c[3]
            sno -= 1
            x -= 1
            y -= 1

            p_x, p_y = dsu[sno].find(x), dsu[sno].find(y)
            if(p_x != p_y):
                dsu[sno].join(x, y)
                val = st.query(sno, sno + 1)
                val -= 1
                st.assign(sno, val)
        else:
            l, r = c[1], c[2]
            print(st.query(l - 1, r))

if __name__=="__main__":
    solve()

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    flag = True
    sm = 0
    for i in range(n - 1):
        if(a[i] >= 180):
            flag = False
        sm += a[i]
    if(flag and sm < (n - 2)*180 and ((n - 2)*180) - sm < 180):
        print(((n - 2)*180) - sm)
    else:
        print(-1)

#include<bits/stdc++.h>

using namespace std;

void solve(){
    // n >= 3
    long long n; cin >> n;
    long long sm = 0;
    bool flag = false;
    for(long long i = 0; i < n - 1; i++){
        long long x; cin >> x;
        sm += x;
        if(x >= 180) flag = true;
    }
    
    if(flag){
        cout << (-1) << "\n";
        return;
    }
    
    if(sm < (n - 2)*180 and ((n-2)*180) - sm < 180){
        cout << ((n-2)*180) - sm << "\n";
    } else {
        cout << (-1) << "\n";
    }
}

int main(){
    // For Fast IO
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    long long T; cin >> T;
    while(T--)
    solve();

    return 0;
}

from collections import defaultdict
for _ in range(int(input())):
    n = input()
    dt = defaultdict(int)
    for i in n:
        dt[ord(i)] += 1
    print(len(dt))

#include <bits/stdc++.h>
using namespace std ;
int main(){
    int t ; cin >> t ;
    while(t--){
        set<char> s ;
        string st ; cin >> st ;
        for(auto x : st){
            s.insert(x);
        }
        cout << s.size() << endl ;
    }
    return 0 ;
}

n = int(input())
a = list(map(int, input().split()))
i, j, flag  = 0, n - 1, True
while(i < j):
    if(a[i] != a[j]):
        flag = False
        print("L LAG GAYE")
        break
    i += 1
    j -= 1
if(flag):
    print("YOU WILL GET ACTION")

#include <bits/stdc++.h>
using namespace std ;
int main(){
    int t = 1 ;
    while(t--){
        int n ; cin >> n ;
        int arr[n], b[n];
        for(int i = 0 ; i < n ; i++){
            cin >> arr[i];
        }
        bool ans = true;
        for(int i = 0 ; i <= n/2 ; i++){
            if(arr[i] != arr[n-i-1]){
                ans = false;
                break;
            }
        }
        (ans)?cout << "YOU WILL GET ACTION\n":cout << "L LAG GAYE\n";
    }
    return 0 ;
}

for _ in range(int(input())):
    n = int(input())
    a = ''.join(sorted(list(map(str, input().split())), reverse = True))
    print(a)

#include <bits/stdc++.h>
using namespace std ;
int main(){
    int t = 1 ; cin >> t ;
    while(t--){
        int n ; cin >> n ;
        int arr[n];
        for(int i = 0 ; i < n ; i++){
            cin >> arr[i];
        }
        sort(arr, arr+n, greater<int>());
        for(int i = 0 ; i < n ; i++){
            cout << arr[i];
        }cout << endl;
    }
    return 0 ;
}

n = int(input())
a = input()
ones, twos = 0, 0
for i in a:
    if i == '0':
        ones += 1
    else:
        twos += 1
if(n % 2 == 0 and twos == ones):
    print("YES")
elif(n % 2 == 1 and (twos + 1 == ones or ones + 1 == twos)):
    print("YES")
else:
    print("NO")

#include <bits/stdc++.h>
using namespace std ;
int main(){
    int t = 1 ;
    while(t--){
        int n ; cin >> n ;
        string s ; cin >> s ;
        (abs(count(s.begin(),s.end(), '0') - (count(s.begin(), s.end(), '1'))) <= 1)?cout << "YES":cout << "NO";
    }
    return 0 ;
}

n, q = map(int, input().split())
a = list(map(int, input().split()))
pre = [ 0 for i in range(n) ]
sm = 0
for i in range(n):
    sm ^= a[i]
    pre[i] = sm

for _ in range(q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    if(l - 1 < 0):
        print(pre[r])
    else:
        print(pre[r]^pre[l-1])

#include <bits/stdc++.h>
using namespace std ;
int main(){
    int t = 1 ;
    while(t--){
        int n, q ; cin >> n >> q;
        vector<int> v(n);
        for(auto &x : v){
            cin >> x ;
        }
        for(int i = 1 ; i < n ; i++){
            v[i] = (int)(v[i]^v[i-1]);
        }

        while(q--){
            int l , r ; cin >> l >> r ;
            if(l == 1){
                cout << v[r-1] << endl;
                continue;
            }
            cout << int(v[r-1]^v[l-2]) << endl;
        }
    }
    return 0 ;
}