#include<bits/stdc++.h>
using namespace std;
 
unsigned int swapBitsInPair(unsigned int x) {
    return ((x & 0b10101010) >> 1) |
            ((x & 0b01010101) << 1);   
}
 
int main() {
    unsigned int x = 4;
    cout << swapBitsInPair(x);   
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define INT_SIZE 32
 
int getSingle(int arr[], int n) {
    int result = 0;
    int x, sum;

    for (int i = 0; i < INT_SIZE; i++) {
        sum = 0;
        x = (1 << i);
        for (int j = 0; j < n; j++) {
            if (arr[j] & x)
                sum++;
        }
        
        if ((sum % 3) != 0)
            result |= x;
    }
 
    return result;
}

int main(){
    int arr[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The element with single occurrence is " << getSingle(arr, n);
    return 0;
}

#include <iostream>
using namespace std;
 
int *multiply(int A[], int B[], int m, int n) {
   int *prod = new int[m+n-1];
   for (int i = 0; i<m+n-1; i++)
     prod[i] = 0;
     for (int i=0; i<m; i++) {
     for (int j=0; j<n; j++)
         prod[i+j] += A[i]*B[j];
   }
 
   return prod;
}
 
void printPoly(int poly[], int n) {
    for (int i=0; i<n; i++) {
       cout << poly[i];
       if (i != 0)
        cout << "x^" << i ;
       if (i != n-1)
       cout << " + ";
    }
}
 
int main() {
    int A[] = {5, 0, 10, 6};
    int B[] = {1, 2, 4};
    int m = sizeof(A)/sizeof(A[0]);
    int n = sizeof(B)/sizeof(B[0]);
 
    cout << "First polynomial is n";
    printPoly(A, m);
    cout << "nSecond polynomial is n";
    printPoly(B, n);
 
    int *prod = multiply(A, B, m, n);
 
    cout << "nProduct polynomial is n";
    printPoly(prod, m+n-1);
 
    return 0;
}

#include <iostream>
#include <ctime>
using namespace std;

int getRandom(int x, int y) {
    srand(time(NULL));
    return (x + rand()%(y-x+1));
}

int randomizedBinarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = getRandom(l, r);
        if (arr[m] == x)  return m;

        if (arr[m] < x) l = m + 1;

        else r = m - 1;
    }
    return -1;
}
 
int main(void) {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr)/ sizeof(arr[0]);
    int x = 10;
    int result = randomizedBinarySearch(arr, 0, n-1, x);
    (result == -1)? printf("Element is not present in array") : printf("Element is present at index %d", result);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
long countWays(int n, int k) {
    long dp[n + 1];
    memset(dp, 0, sizeof(dp));
    long long mod = 1000000007;
 
    dp[1] = k;
    dp[2] = k * k;
 
    for (int i = 3; i <= n; i++) {
        dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod;
    }
 
    return dp[n];
}
 
int main() {
    int n = 3, k = 2;
    cout << countWays(n, k) << endl;
    return 0;
}