loading...

Daily Coding Challenge #26

wingkwong profile image wkw ・2 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
Codeforces Round #647 (Div. 2) - Thanks, Algo Muse! - A. Johnny and Ancient Computer
https://codeforces.com/contest/1362/problem/A
*/

#include <bits/stdc++.h>
using namespace std; 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)

long long solve(long long a, long long b){
    int ans=0;
    // multiply a by 8, 4, and 2 to see if a can be b or not
    // if so, print the number of operations
    // else, print -1
    while(a*8<=b) {
        ans++;
        a*=8;
    }
    while(a*4<=b) {
        ans++;
        a*=4;
    }
    while(a*2<=b) {
        ans++;
        a*=2;
    }   

    if(a==b){
        cout << ans << "\n";
    } else {
        cout << -1 << "\n";
    }
}

int main()  
{ 
    FAST_INP;
    int t;
    long long a,b;
    cin >> t;
    while(t--){
        cin >> a >> b;
        // if a==b, no operation
        if(a==b) {
            cout << 0 << "\n";
            continue;
        }
        // by arranging the order, we only need to take care of 3 operations
        solve(min(a,b), max(a,b));
    }
    return 0;
} 

Enter fullscreen mode Exit fullscreen mode

/*
Codeforces Round #647 (Div. 2) - Thanks, Algo Muse! - B. Johnny and His Hobbies
https://codeforces.com/contest/1362/problem/B
*/

#include <bits/stdc++.h>
using namespace std; 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)

int main()  
{ 
    FAST_INP;
    int t,n;
    cin >> t;
    while(t--){
        // brute force approach
        int ans=-1;
        cin >> n;
        vector<int> a(n),b(n);
        for(int i=0;i<n;i++) cin >> a[i];
        // sort input 
        sort(a.begin(),a.end());
        for(int i=1;i<1024;i++){
            int f=true;
            // calculate each possible value
            for(int j=0;j<n;j++){
                b[j]=a[j]^i;
            }
            // sort XOR result array
            sort(b.begin(),b.end());
            // if they are not same, the current i is not the correct answer
            for(int i=0;i<n;i++){
                if(a[i]!=b[i]){
                    f=false;
                    break;
                }
            }
            // if the ans is found, skip the rest of the operations
            if(f){
                ans=i;
                break;
            } 
        }
        if(ans) cout << ans << "\n";
        else cout << -1 << "\n";
    }
    return 0;
} 

Enter fullscreen mode Exit fullscreen mode

/*
Codeforces Round #647 (Div. 2) - Thanks, Algo Muse! - C. Johnny and Another Rating Drop
https://codeforces.com/contest/1362/problem/C
*/
#include <bits/stdc++.h>
using namespace std; 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)


int main()  
{ 
    FAST_INP;
    int t;
    long long n;
    cin >> t;
    while(t--){
        cin >> n;
        int ans=0;
        // list out the first 16 binary numbers including 0
        // we can see the pattern for each significant bit changes
        // 1st: 0->1->0->1->0->1....            (change every 1 number)
        // 2nd: 0->0->1->1->0->0->1->1->...     (change every 2 numbers)
        // 3rd: 0->0->0->0->1->1->1->1->...     (change every 4 numbers)
        while(n){
            ans+=n;
            n>>=1;
        }
        cout << ans << "\n";
    }
    return 0;
} 

Enter fullscreen mode Exit fullscreen mode

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / hackerrank

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / codeforces

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / atcoder

Migrated to https://github.com/wingkwong/competitive-programming

Discussion

pic
Editor guide