Skip to content

Instantly share code, notes, and snippets.

@dipta10

dipta10/CodeChef TAAND #bitmanipulation.cpp

Created November 7, 2018 08:49
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dipta10/d9f730a6b2bff4d98fe937ab911071b5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dipta10/d9f730a6b2bff4d98fe937ab911071b5 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dipta10 created this gist Nov 7, 2018.
    49 changes: 49 additions & 0 deletions CodeChef TAAND #bitmanipulation.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@
    /*
    * CodeChef TAAND
    * link: https://www.codechef.com/problems/TAAND
    * editorial: https://discuss.codechef.com/questions/48551/taand-editorial
    */

    #include <stdio.h>
    #include <bits/stdc++.h>
    #define fin freopen("input", "r", stdin)
    #include <vector>

    using namespace std;
    int n;

    int sol(int index, vector<int>& ar, vector<int>& flag) {
    // basecase
    if (index == -1) return 0;
    int ans = 0;
    int total = 0;
    for (int i = 0; i < n; ++i) {
    if (flag[i] == 0) {
    if (ar[i] & (1 << index)) {
    total++;
    }
    }
    }
    if (total >= 2) {
    ans += (1 << index);
    for (int i = 0; i < n; ++i) {
    if ((ar[i] & (1 << index)) == 0) {
    flag[i] = 1;
    }
    }
    }
    return ans + sol(index - 1, ar, flag);
    }

    int main()
    {
    cin >> n;
    vector<int> ar(n);
    vector<int> flag(n);
    //for (int i = 0; i < n; ++i) cin >> ar[i];
    for (int& x : ar) cin >> x;

    cout << sol(30, ar, flag) << endl;

    return 0;
    }