(Compute the greatest common divisor) Another solution for Listing 5.10 to find the greatest common divisor (GCD) of two integers n1 and n2 is as follows: First find d to be the minimum of n1 and n2, then check whether d, d-1, d-2, . . . , 2, or 1 is a divisor for both n1 and n2 in this order. The first such common divisor is the greatest common divisor for n1 and n2. Write a program that prompts the user to enter two positive integers and displays the GCD.

#include<iostream>
using namespace std;
bool issafe(int** arr,int x,int y,int n){
    for(int row=0;row<=x;row++){
        if(arr[x][y]==1){
            return false;
        }
    }
    int row=x;
    int col=y;
    while(row>=0 && col>=0){
        if(arr[row][col]==1){
            return false;
        }
        row--;
        col--;
    }
     row=x;
     col=y;
    while(row>=0 && col<n){
        if(arr[row][col]==1){
            return false;
        }
        row--;
        col++;
    }
    return true ;
}
bool nqueen(int** arr,int x,int n){
    if(x>=n){
        return true;
    }
    for(int col=0;col<=n;col++){
        if(issafe(arr,x,col,n)){
            arr[x][col]==1;
            if(nqueen(arr,x+1,n)){
                return true;
            }
            arr[x][col]=0;  //backtracking
            
        }
    }
    return false;
}
int main(){
    int n;
    cin>>n;
    int** arr=new int*[n];
    for(int i=0;i<n;i++){
        arr[i]=new int[n];
        for(int j=0;j<n;j++){
            arr[i][j]=0;

        }
    }
    if(nqueen(arr,0,n)){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<arr[i][j]<<"";
            }cout<<endl;
        }
    }


    return 0;
}

#include <iostream>
#include<cmath>
#include<ctime>
#include<string>
#include <iomanip>
#include <fstream>

using namespace std;




void decToBinary(int n)
{
    // array to store binary number 
    int binaryNum[3][3];
    
    //converting to binary 
    for (int i = 0; i < 3; i++) 
    {
        for (int j = 0; j < 3; j++)
        {
            binaryNum[i][j] = n % 2;
            n = n / 2;

        }
     }       

    // printing binary> array in reverse order 
    for (int i = 3-1; i >= 0; i--){
        for (int j = 3 - 1; j >= 0; j--)
        {
            if (binaryNum[i][j] == 0)
                cout << "H" << " ";
            else
                cout << "T" << " ";
        }
        cout << endl;
    }
    
 }

int main()
{
    int n;
    cout << "Enter a decimal number between 1 and 512 ";
    cin >> n;

    decToBinary(n);
    return 0;
}

#include<iostream>
using namespace std;

int sum(int arr[], int a);

int main() {
    int arr[1000], n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        cout << sum(arr, n);
    }
}
int sum(int arr[], int a) {
    int i;
    sum = 0;
    for (i=0; i<n; ++i) {
        sum += arr[i];
    }
    return sum;
}#include<iostream>
using namespace std;

int sum(int arr[], int a);

int main() {
    int arr[1000], n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        cout << sum(arr, n);
    }
}
int sum(int arr[], int a) {
    int i;
    sum = 0;
    for (i=0; i<n; ++i) {
        sum += arr[i];
    }
    return sum;
}

int maxSubArraySum(int a[], int size) 
{ 
int max_so_far = 0, max_ending_here = 0; 
for (int i = 0; i < size; i++) 
{ 
	max_ending_here = max_ending_here + a[i]; 
	if (max_ending_here < 0) 
		max_ending_here = 0; 

	/* Do not compare for all elements. Compare only 
		when max_ending_here > 0 */
	else if (max_so_far < max_ending_here) 
		max_so_far = max_ending_here; 
} 
return max_so_far; 
} 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
 
function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    
    if (head === null)
        return null;
    
    let currPtr = head, prevPtr = null;
    
    while (left > 1) {
        prevPtr = currPtr;
        currPtr = currPtr.next;
        
        left--;
        right--;
    }
    
    let tailPtr = currPtr, connPtr = prevPtr, thirdPtr: ListNode | null = null;
    
    while (right > 0) {
        thirdPtr = currPtr.next;
        currPtr.next = prevPtr;
        prevPtr = currPtr;
        currPtr = thirdPtr;
        
        right--;
    }
    
    if (connPtr)
        connPtr.next = prevPtr;
    else
        head = prevPtr;
    
    tailPtr.next = currPtr;
    
    return head;
};

#include<iostream>
using namespace std;
bool issafe(int** arr,int x,int y,int n){
    for(int row=0;row<x;row++){
        if(arr[row][y]==1) return false;
    }
    int row=x-1;
    int col=y-1;
    while(row>=0 && col>=0){
        if(arr[row][col]==1)return false;
        row--;
        col--;
    }
     row=x-1;
     col=y+1;
    while(row>=0 && col<n){
        if(arr[row][col]==1)  return false;
        row--;
        col++;
    }
    return true ;
}
bool nqueen(int** arr,int n,int x=0){
    if(x>=n) return true;
    for(int col=0;col<n;col++){
        if(issafe(arr,x,col,n)){
            arr[x][col]=1;
            if(nqueen(arr,n,x+1)) return true;
            arr[x][col]=0;  //backtracking
        }
    }
    return false;
}
int main(){
    int n;
    cin>>n;
    int **arr=new int*[n];
    for(int i=0;i<n;i++){
        arr[i]=new int[n];
        for(int j=0;j<n;j++) arr[i][j]=0;
    }
    if(nqueen(arr,n)){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) cout<<arr[i][j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
	int search(vector<int> arr,int n,int x){
		int low=0,high=n-1;
		while(low<=high){
			int mid=low+(high-low)/2;
			if(arr[mid]>x){
				high=mid-1;
			}
			else if(arr[mid]<x){
				low=mid+1;
			}
			else{
				return mid;
			}
		}
		return low;
	}
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
		vector<int> ans;
		int n=arr.size();
        int i=search(arr,n,x);
		int l=i-1,r=i;
		while(k>0){
			if(l<0 || (r<n && abs(arr[l]-x)>abs(arr[r]-x))){
				r++;
			}
			else{
				l--;
			}
			k--;
		}
		l++;
		while(l<r){
			ans.push_back(arr[l]);
			l++;
		}
		return ans;
    }
};
int main(){
	Solution s;
	vector<int> a={1,2,3,4,5};
	int k=3,x=2;
	vector<int> ans=s.findClosestElements(a,k,x);
	for(auto i:ans){
		cout<<i<<" ";
	}cout<<endl;
	return 0;
}

#include<iostream>
#include<unordered_map>
#include<queue>
#define rep(i,a,b) for(long int i=a;i<b;i++)
#define ull unsigned long long
using namespace std;

int main()
{
    long int a,b,c;
    cin>>a>>b>>c;
    unordered_map<int,int> um;
    // int *array1=new int[a];
    int *array1=new int[a];
    int *array2=new int[b];
    int *array3=new int[c];
    rep(i,0,a) {
        cin>>array1[i];
         um[array1[i]]++;
    }
    rep(i,0,b) {
        cin>>array2[i];
    }
    rep(i,0,c) {
        cin>>array3[i];
    }
    queue<int> output;
    long int count=0;
    long  int i=0,j=0;
    while(i<b && j<c){
        if(array2[i]>array3[j]){
            if(um.find(array3[j])!=um.end()){
                count++;
                output.push(array3[j]);
            } 
                j++;
        }
        else if(array2[i]<array3[j]){
            if(um.find(array2[i])!=um.end()){
                count++;
                output.push(array2[i]);
            } 
                i++;
        }
        else{
            count++;
            output.push(array2[i]);
            i++;
            j++;
        }
    }
    while(i<b){
        if(um.find(array2[i])!=um.end()) {
        count++;
        output.push(array2[i]);
        }
        i++;
    }
    while(j<c){
        if(um.find(array3[j])!=um.end()) {
        count++;
        output.push(array3[j]);
        }
        j++;
    }
    cout<<count<<endl;
   while(!output.empty())
   {
       cout<<output.front()<<endl;
       output.pop();
   }

return 0;
}

// python
def isbright(image, dim=10, thresh=0.5):
    # Resize image to 10x10
    image = cv2.resize(image, (dim, dim))
    # Convert color space to LAB format and extract L channel
    L, A, B = cv2.split(cv2.cvtColor(image, cv2.COLOR_BGR2LAB))
    # Normalize L channel by dividing all pixel values with maximum pixel value
    L = L/np.max(L)
    # Return True if mean is greater than thresh else False
    return np.mean(L) > thresh

// c++
bool rockface_image_is_bright(cv::Mat img_mat, int dim, float threshold)
{
	// Resize image to 10x10
	cv::resize(img_mat, img_mat, { dim, dim });

	// Convert color space to LAB format and extract L channel
	cv::cvtColor(img_mat, img_mat, cv::COLOR_RGB2Lab);
	cv::Mat labchannel[3];
	cv::split(img_mat, labchannel);

	cv::imshow("L", labchannel[0]);
	cv::waitKey(0);

	// Normalize L channel by dividing all pixel values with maximum pixel value
	cv::Mat L;
	cv::normalize(labchannel[0], L, 0, 1, cv::NORM_MINMAX);

	// Return True if mean is greater than thresh else False
	float brightness = cv::mean(L).val[0];
	std::cout << "brightness: " << brightness << std::endl;
	return brightness > threshold;
}

void reverseStr(string& str)
{
    int n = str.length();
 
    // Swap character starting from two
    // corners
    for (int i = 0; i < n / 2; i++)
        swap(str[i], str[n - i - 1]);
}
 

class Solution
{
    public:
    void merge(int arr[], int l, int m, int r)
    {
         int n1=m-l+1; 
         int n2=r-m;
         // Initialization of temp arrays
         int L[n1],R[n2];
         // Initialization of first subarray
         for(int i=0;i<n1;i++)
         L[i]=arr[l+i];
         // Initialization of second subarray
         for(int j=0;j<n2;j++)
         R[j]=arr[m+1+j];
         int i=0,j=0,k=l;
         //Sorting the array using subarrays
         while(i<n1&&j<n2){
             if(L[i]<R[j]){
                 arr[k]=L[i];
                 i++;
             }
             else {
                 arr[k]=R[j];
                 j++;
             }
             k++;
         }
         //Remaining elements added to the array
         while(i<n1){
             arr[k]=L[i];
             i++;k++;
         }
         while(j<n2){
             arr[k]=R[j];
             j++;k++;
         }
    }
    public:
    void mergeSort(int arr[], int l, int r)
    {
        if(l>=r)
        return; //returns recursively
        int m=l+(r-l)/2;
        mergeSort(arr,l,m);
        mergeSort(arr,m+1,r);
        merge(arr,l,m,r);
    }
};

class Solution
{
    public:
    void insertionSort(int arr[], int n)
    {
        int value,hole;
        for(int i=0;i<n;i++){
            value=arr[i];hole=i;
        while(hole>0&&arr[hole-1]>value){
            arr[hole]=arr[hole-1];
            hole--;
        }
        arr[hole]=value;
        }
    }
};

class Solution
{
    public:
    int select(int arr[], int i)
    {
        int max = arr[0], ind = 0;
    int j;
    for ( j=1; j<=i; j++)
    {
        if (arr[j] > max)
        {
           ind = j;
           max = arr[j];
        }
    }
    return ind;
    }
     
    void selectionSort(int arr[], int n)
    {
       int i, j;
   for (i = n-1; i >=0; i--)      
   {
        int j = select(arr, i);
        swap(&arr[i], &arr[j]);
   }
    }
};

class Solution
{
    public:
    //Function to sort the array using bubble sort algorithm.
    void bubbleSort(int arr[], int n)
    {
      int flag=0;
    for(int k=1;k<=n-1;k++){
        for(int j=0;j<=n-k-1;j++){
            if(arr[j]>arr[j+1]){
                swap(&arr[j],&arr[j+1]);
              flag=1;
            }
        }
      if(flag==0)
        break;
    }
    }
    void swap(int *xp,int *yp){
        int temp=*xp;
        *xp=*yp;
        *yp=temp;
    }
};

class int_ptr_wrapper
{
public:
    int_ptr_wrapper(int value = 0) :
    mInt(new int(value))
    {}

    // note! needs copy-constructor and copy-assignment operator!

    ~int_ptr_wrapper()
    {
        delete mInt;
    }

private:
    int* mInt;
};