IBM Oa Help | Oa Exam Helper

In py

#include <bits/stdc++.h> using namespace std; int equalzeroandone(vector<int>v){     int n=v.size();     for(int i=0;i<n;i++){         if(v[i]==0){             v[i]=-1;         }     }     int sum=0;     int ans=-1;    map<int,int>mp;     for(int i=0;i<n;i++){         sum+=v[i];         if(sum==0){             ans=i+1;         }         if(mp.find(sum)!=mp.end()){             ans=max(ans,i-mp[sum]);         }         else{             mp[sum]=i;         }     }     return ans; } int main() {     int n;     cin>>n;     vector<int>v(n);     for(int i=0;i<n;i++){         cin>>v[i];     }     cout<<equalzeroandone(v); } Equal number of zero Infosys

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll solve(string s1, string s2) {
    ll m = s1.length();
    ll n = s2.length();
    vector<vector<ll>>dp(m+1,vector<ll>(n + 1));
    for (ll i=1;i<= m;i++) {
        dp[i][0]=i;
    }
    for (ll j = 1; j <= n;j++) {
        dp[0][j] = j; 
    }
    for (ll i = 1; i <= m; ++i) 
    {
        for (ll j = 1; j <= n; ++j) 
        {
            if (s1[i - 1] == s2[j - 1]) 
            {
                dp[i][j] = dp[i - 1][j - 1];
            } 
            else 
            {
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]); 
                if (i > 1 && j > 1 && s1[i - 1] == s2[j - 2]) 
                {
                    dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j - 2]); 
                }
                if (i > 1 && j > 1 && s1[i - 2] == s2[j - 1]) 
                {
                    dp[i][j] = min(dp[i][j], 1 + dp[i - 2][j - 1]); 
                }    
            }
        }
    }
    return dp[m][n];
}

signed main() 
{
    string s1,s2; cin>>s1>>s2;
    cout<<solve(s1,s2)<<endl;
    
    return 0;
}

//string operation

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
struct FenwickTree {
    vector<ll> bit;
    ll n;
    FenwickTree(ll size) {
        n = size;
        bit.assign(n + 1, 0);
    }

    void update(ll idx, ll val) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] = max(bit[idx], val);
    }
    ll query(ll idx) {
        ll res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res = max(res, bit[idx]);
        return res;
    }
};
ll solve(vector<ll>& a)
 {
    ll n=a.size();
    vector<pair<ll,ll>>ia(n);
    for (ll i=0;i<n;i++) 
    {
        ia[i] = make_pair(a[i], i);
    }
    sort(ia.begin(),ia.end(),[](const pair<ll,ll>&p1,const pair<ll,ll>&p2) {
        return p1.first<p2.first;
    });
    FenwickTree fenwick(n);
    ll maxBeauty=0;
    for (ll i=0;i<n;i++) 
    {
        ll val=ia[i].first;
        ll og=ia[i].second;
        ll beauty=0;
        for (ll j=og-1;j>=0;j--) 
        {
            if (__gcd(abs(a[j]),abs(a[og]))>1) {
                beauty=max(beauty,fenwick.query(j+1)+(a[og]-a[j])*(a[og]-a[j]) % MOD);
            }
        }
        fenwick.update(og + 1, beauty);
        maxBeauty = max(maxBeauty, beauty);
    }
    return maxBeauty;
}
signed main() 
{
    ll n; cin>>n;
    vector<ll>a(n);
    for (ll i=0;i<n;i++)  cin>>a[i];
    cout<<solve(a)<<endl;
    return 0;
}

//subsequnce beauty

subset sum

const int MOD 1000000007; int subsetSumCount(const vector<int>& A, int L, int R, int K) { vector<int> dp(K+1, 0); dp[0] = 1; for (int i=L; i<=R; ++i) { for (int j = K; j >= A[1]; --j) { dp[j] = (dp[j] + dp[j- A[i]]) % MOD; } } return dp[K];} int findXOR(int n, int Q, const vector<int>& A, const vector<vector<int>>& B) { int result = 0; for (const auto& query: B) { int L= query [0] - 1; int R= query [1] -1; int K = query[2]; int P=subsetSumCount(A,L,R,K); result ^= P; } return result; }

#include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> using namespace std; void dfs(int x, int y, vector<unordered_set<int>>& v, unordered_map<int, vector<int>>& t, vector<int>& a) { unordered_set<int> s; s.insert(a[x]); for (int z : t[x]) { if (z != y) { dfs(z, x, v, t, a); for (int elem : v[z]) { s.insert(elem); } } } v[x] = s; } int find_sets(int n, vector<int>& a, vector<int>& p) { unordered_map<int, vector<int>> t; for (int i = 1; i < n; ++i) { t[p[i]].push_back(i); t[i].push_back(p[i]); } vector<unordered_set<int>> v(n); dfs(0, -1, v, t, a); int r = 0; for (int i = 1; i < n; ++i) { int y = p[i]; if (y < v.size()) { unordered_set<int>& s1 = v[i]; unordered_set<int>& s2 = v[y]; unordered_set<int> s_diff; for (int elem : s2) { if (s1.find(elem) == s1.end()) { s_diff.insert(elem); } } if (s_diff.empty()) { ++r; } } } return r; } int main() { int n; cin >> n; vector<int> a(n); vector<int> p(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < n; ++i) { cin >> p[i]; } int result = find_sets(n, a, p); cout << result << endl; return 0; }. //Tree dupilcates

Binaty counting

dp[i+1][0][0][(j + addv)%k][pv+1] += dp[i][1][0][j][pv]; dp[i+1][0][0][(j + addv)%k][pv+1] %= mod; } else{ dp[i+1][1][0][(j + addv)%k][pv+1] += dp[i][1][0][j][pv]; dp[i+1][1][0][(j + addv)%k][pv+1] %= mod; } // le = 0, re = 1 if(r[i] == '0'){ dp[i+1][0][1][j][pv-1] += dp[i][0][1][j][pv]; dp[i+1][0][1][j][pv-1] %= mod; } else{ dp[i+1][0][1][(j + addv)%k][pv+1] += dp[i][0][1][j][pv]; dp[i+1][0][1][(j + addv)%k][pv+1] %= mod; dp[i+1][0][0][j][pv-1] += dp[i][0][1][j][pv]; dp[i+1][0][0][j][pv-1] %= mod; } // le = 0, re = 0 dp[i+1][0][0][j][pv-1] += dp[i][0][0][j][pv]; dp[i+1][0][0][j][pv-1] %= mod; dp[i+1][0][0][(j + addv)%k][pv+1] += dp[i][0][0][j][pv]; dp[i+1][0][0][(j + addv)%k][pv+1] %= mod; } } } } int ans = 0; for(int i = 0; i <= n; i++){ for(int j = 0; j < 2; j++){ for(int z = 0; z < 2; z++){ ans += dp[n][j][z][0][i]; ans %= mod; } } } return ans; } int32_t main(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int m, n, k; cin>>m>>n>>k; string l, r; cin>>l>>r; cout<

#include<bits/stdc++.h> #define pb push_back #define int long long using namespace std; const int mod = 1e9+7; const int N = 1e2 + 5; int get_ans(int m, int n, int k, string l, string r){ int dp[n+1][2][2][k][n+1]; for(int i = 0; i <= n; i++){ for(int j = 0; j < k; j++){ for(int pv = 0; pv <= n; pv++){ dp[i][0][0][j][pv] = dp[i][0][1][j][pv] = dp[i][1][0][j][pv] = dp[i][1][1][j][pv] = 0; } } } vector<int> add(n+1); add[0] = (1%k); for(int i = 1; i <= n; i++){ add[i] = (add[i-1] * 2)%k; } if(m == n) dp[1][1][1][(add[n-1])%k][1] = 1; else{ dp[1][0][1][(add[n-1])%k][1] = 1; for(int i = 1; i < n; i++){ if(l[i] == '1'){ dp[i+1][1][0][add[n - i - 1]%k][1] = 1; break; } else dp[i+1][0][0][add[n - i - 1]%k][1] = 1; } } string ll = ""; for(int i = m; i < n; i++){ ll += '0'; } for(int i = 0; i < l.size(); i++){ ll += l[i]; } l = ll; for(int i = 0; i < n; i++){ int addv = add[(n - i - 1)]; for(int j = 0; j < k; j++){ for(int pv = 0; pv < n; pv++){ if(pv == 0){ // le = 1, re = 1 if(l[i] != r[i]){ dp[i+1][0][1][(j + addv)%k][pv+1] += dp[i][1][1][j][pv]; dp[i+1][0][1][(j + addv)%k][pv+1] %= mod; } else{ if(l[i] == '0'){ } else{ dp[i+1][1][1][(j + addv)%k][pv+1] += dp[i][1][1][j][pv]; dp[i+1][1][1][(j + addv)%k][pv+1] %= mod; } } // le = 1, re = 0 if(l[i] == '0'){ dp[i+1][0][0][(j + addv)%k][pv+1] += dp[i][1][0][j][pv]; dp[i+1][0][0][(j + addv)%k][pv+1] %= mod; } else{ dp[i+1][1][0][(j + addv)%k][pv+1] += dp[i][1][0][j][pv]; dp[i+1][1][0][(j + addv)%k][pv+1] %= mod; } // le = 0, re = 1 if(r[i] == '0'){ } else{ dp[i+1][0][1][(j + addv)%k][pv+1] += dp[i][0][1][j][pv]; dp[i+1][0][1][(j + addv)%k][pv+1] %= mod; } // le = 0, re = 0 dp[i+1][0][0][(j + addv)%k][pv+1] += dp[i][0][0][j][pv]; dp[i+1][0][0][(j + addv)%k][pv+1] %= mod; } else{ // le = 1, re = 1 if(l[i] != r[i]){ dp[i+1][1][0][j][pv-1] += dp[i][1][1][j][pv]; dp[i+1][1][0][j][pv-1] %= mod; dp[i+1][0][1][(j + addv)%k][pv+1] += dp[i][1][1][j][pv]; dp[i+1][0][1][(j + addv)%k][pv+1] %= mod; } else{ if(l[i] == '0'){ dp[i+1][1][1][j][pv-1] += dp[i][1][1][j][pv]; dp[i+1][1][1][j][pv-1] %= mod; } else{ dp[i+1][1][1][(j + addv)%k][pv+1] += dp[i][1][1][j][pv]; dp[i+1][1][1][(j + addv)%k][pv+1] %= mod; } } // le = 1, re = 0 if(l[i] == '0'){ dp[i+1][1][0][j][pv-1] += dp[i][1][0][j][pv]; dp[i+1][1][0][j][pv-1] %= mod;

def is_palindrome(s): return s == s[::-1] def longest_palindrome_from_substrings(A): palindromes = [] pairs = [] max_single_palindrome = "" for s in A: if is_palindrome(s): palindromes.append(s) if len(s) > len(max_single_palindrome): max_single_palindrome = s for i in range(len(A)): for j in range(i + 1, len(A)): combined1 = A[i] + A[j] combined2 = A[j] + A[i] if is_palindrome(combined1): pairs.append(combined1) if is_palindrome(combined2): pairs.append(combined2) longest_palindrome = max_single_palindrome for p in pairs: if len(p) > len(longest_palindrome): longest_palindrome = p return longest_palindrome

Palindomic substring

#include <bits/stdc++.h> #define ll long long using namespace std; ll solve(string&s) { ll cnt1=0,cnt0=0; for(auto&it:s) { if(it=='1') cnt1++; else cnt0++; } ll n=s.size(),ans=0; for(ll i=0;i<n;i++) { if(s[i]=='1') { if(cnt0==0) { ans=n-1-i+1; break; } else{ cnt0--; } } else { if(cnt1==0) { ans=n-1-i+1; break; } else cnt1--; } } return ans; } signed main() { string s; cin>>s; cout<<solve(s); return 0; } //swap and delete string

cpp Prime sum

using namespace std; int main() { int tt = 1; for (int t = 1; t <= tt; t++) { int n; cin >> n; vector a(n); vector prime(301, 0); prime[1] = 1; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 2; i <= 300; i++) { if (prime[i] == 0) { for (int j = 2 * i; j <= 300; j += i) { prime[j] = 1; } } } unordered_map count; int cnt = 0; map> map; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = a[i] + a[j]; if (prime[sum] == 0) { cnt++; count[a[i]]++; count[a[j]]++; map[a[i]].push_back(a[j]); map[a[j]].push_back(a[i]); } } } vector> list(count.begin(), count.end()); sort(list.begin(), list.end(), [](const pair& entry1, const pair& entry2) { return entry2.second > entry1.second; }); count.clear(); for (auto& entry : list) { count[entry.first] = entry.second; } int ans = 0; while (cnt > 0) { auto firstEntry = *count.begin(); cnt -= firstEntry.second; ans++; count[firstEntry.first] = 0; for (int it : map[firstEntry.first]) { count[it]--; } list.assign(count.begin(), count.end()); sort(list.begin(), list.end(), [](const pair& entry1, const pair& entry2) { return entry2.second > entry1.second; }); count.clear(); for (auto& entry : list) { count[entry.first] = entry.second; } } cout << n - ans << endl; } return 0; }

Prime sum

import java.util.*; public class PrimeSumOptimal { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] A = new int[N]; for (int i = 0; i < N; i++) { A[i] = sc.nextInt(); } System.out.println(maxNonPrimeSumSubset(A, N)); sc.close(); } private static boolean[] isPrime; private static void sieve(int maxLimit) { isPrime = new boolean[maxLimit + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int p = 2; p * p <= maxLimit; p++) { if (isPrime[p]) { for (int i = p * p; i <= maxLimit; i += p) { isPrime[i] = false; } } } } private static boolean isPrime(int num) { return isPrime[num]; } private static int maxNonPrimeSumSubset(int[] A, int N) { sieve(1000); int maxSubsetSize = 0; for (int bitmask = 0; bitmask < (1 << N); bitmask++) { List<Integer> subset = new ArrayList<>(); for (int i = 0; i < N; i++) { if ((bitmask & (1 << i)) != 0) { subset.add(A[i]); } } boolean validSubset = true; int subsetSize = subset.size(); for (int i = 0; i < subsetSize && validSubset; i++) { for (int j = i + 1; j < subsetSize; j++) { if (isPrime(subset.get(i) + subset.get(j))) { validSubset = false; break; } } } if (validSubset) { maxSubsetSize = Math.max(maxSubsetSize, subsetSize); } } return maxSubsetSize; } }.

choose the sequence

#include <bits/stdc++.h> #define ll long long using namespace std; #define ll long long ll solve(vector<ll>&a) { ll n=a.size(); vector<ll>dp(n, 1); for (ll i=1;i<n;i++) { for (ll j=0;j<i;j++) { if (a[j]<a[i] && __gcd(a[j],a[i])>1) { dp[i]=max(dp[i],dp[j]+1); } } } return *max_element(dp.begin(), dp.end()); } signed main() { ll n; cin>>n; vector<ll>a(n); for(ll i=0;i<n;i++) cin>>a[i]; cout<<solve(a); return 0; }