Advance.txt

 : 
Solution :
# Python  
age=input(int("Age : "))
print(age);
                                                                                                                                               Maintainer : Gaurav-2803
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

0. Create a function that finds the maximum range of a triangle's third edge, where the side lengths are all integers. Note. (side1 + side2) - 1 = maximum range of third edge.
// C++ implementation of the approach
#include <iostream>
using namespace std;

// Function to find the minimum and the
// maximum possible length of the third
// side of the given triangle
void find_length(int s1, int s2)
{

	// Not a valid triangle
	if (s1 <= 0 || s2 <= 0) {
		cout << -1;
		return;
	}
	int max_length = s1 + s2 - 1;
	int min_length = max(s1, s2) - min(s1, s2) + 1;

	// Not a valid triangle
	if (min_length > max_length) {
		cout << -1;
		return;
	}

	cout << "Max = " << max_length << endl;
	cout << "Min = " << min_length;
}

// Driver code
int main()
{
	int s1 = 8, s2 = 5;
	find_length(s1, s2);

	return 0;
}

Solution :

1. You are given an integer 'N', your task is to find and return thr N'th Fibonacci Number using Matrix Exponentiation.
Solution :
//C++ Implementation 

#include<bits/stdc++.h>
using namespace std;


void multiply(int a[3][3], int b[3][3])
{
	
	int mul[3][3];
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			mul[i][j] = 0;
			for (int k = 0; k < 3; k++)
				mul[i][j] += a[i][k]*b[k][j];
		}
	}

	for (int i=0; i<3; i++)
		for (int j=0; j<3; j++)
			a[i][j] = mul[i][j]; 
}

int power(int F[3][3], int n)
{
	int M[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}};


	if (n==1)
		return F[0][0] + F[0][1];

	power(F, n/2);

	multiply(F, F);

	if (n%2 != 0)
		multiply(F, M);


	return F[0][0] + F[0][1] ;
}


int findNthTerm(int n)
{

	int F[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}} ;

	if(n==0)
		return 0;
	if(n==1 || n==2)
		return 1;
	return power(F, n-2);
}

int main()
{
int n;
cin>>n;
cout << findNthTerm(n)<<endl;
return 0;
}


2. Write functions that add, subtract, and multiply two numbers in their digit-list representation (and return a new digit list) using Karatsuba multiplication.
Solution :
// C++ implementation of Karatsuba algorithm for bit string multiplication.
#include<iostream>
#include<stdio.h>

using namespace std;

// FOLLOWING TWO FUNCTIONS ARE COPIED FROM http://goo.gl/q0OhZ
// Helper method: given two unequal sized bit strings, converts them to
// same length by adding leading 0s in the smaller string. Returns the
// the new length
int makeEqualLength(string &str1, string &str2)
{
	int len1 = str1.size();
	int len2 = str2.size();
	if (len1 < len2)
	{
		for (int i = 0 ; i < len2 - len1 ; i++)
			str1 = '0' + str1;
		return len2;
	}
	else if (len1 > len2)
	{
		for (int i = 0 ; i < len1 - len2 ; i++)
			str2 = '0' + str2;
	}
	return len1; // If len1 >= len2
}

// The main function that adds two bit sequences and returns the addition
string addBitStrings( string first, string second )
{
	string result; // To store the sum bits

	// make the lengths same before adding
	int length = makeEqualLength(first, second);
	int carry = 0; // Initialize carry

	// Add all bits one by one
	for (int i = length-1 ; i >= 0 ; i--)
	{
		int firstBit = first.at(i) - '0';
		int secondBit = second.at(i) - '0';

		// boolean expression for sum of 3 bits
		int sum = (firstBit ^ secondBit ^ carry)+'0';

		result = (char)sum + result;

		// boolean expression for 3-bit addition
		carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);
	}

	// if overflow, then add a leading 1
	if (carry) result = '1' + result;

	return result;
}

// A utility function to multiply single bits of strings a and b
int multiplyiSingleBit(string a, string b)
{ return (a[0] - '0')*(b[0] - '0'); }

// The main function that multiplies two bit strings X and Y and returns
// result as long integer
long int multiply(string X, string Y)
{
	// Find the maximum of lengths of x and Y and make length
	// of smaller string same as that of larger string
	int n = makeEqualLength(X, Y);

	// Base cases
	if (n == 0) return 0;
	if (n == 1) return multiplyiSingleBit(X, Y);

	int fh = n/2; // First half of string, floor(n/2)
	int sh = (n-fh); // Second half of string, ceil(n/2)

	// Find the first half and second half of first string.
	// Refer http://goo.gl/lLmgn for substr method
	string Xl = X.substr(0, fh);
	string Xr = X.substr(fh, sh);

	// Find the first half and second half of second string
	string Yl = Y.substr(0, fh);
	string Yr = Y.substr(fh, sh);

	// Recursively calculate the three products of inputs of size n/2
	long int P1 = multiply(Xl, Yl);
	long int P2 = multiply(Xr, Yr);
	long int P3 = multiply(addBitStrings(Xl, Xr), addBitStrings(Yl, Yr));

	// Combine the three products to get the final result.
	return P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2;
}

// Driver program to test above functions
int main()
{
	printf ("%ld\n", multiply("1100", "1010"));
	printf ("%ld\n", multiply("110", "1010"));
	printf ("%ld\n", multiply("11", "1010"));
	printf ("%ld\n", multiply("1", "1010"));
	printf ("%ld\n", multiply("0", "1010"));
	printf ("%ld\n", multiply("111", "111"));
	printf ("%ld\n", multiply("11", "11"));
}


3. Implement the following sorting algorithms: Selection sort, Insertion sort, Merge sort, Quick sort, Stooge Sort.
Solution : 
//Selection Sort,Insertion Sort, Quick Sort using C++
#include<iostream>
using namespace std;

int partition(int a[], int start, int end)   //For Quick Sort
{
    int pivot=a[start];
    int count=0;
    for(int i=start+1;i<=end;i++)
    {
        if (a[i] <= pivot)
            count++;
    }
    int Ipivot = start + count;
    swap(a[Ipivot], a[start]);
    int i = start, j = end;

    while ((i<Ipivot) && (j>Ipivot))
    {
        while (a[i] <= pivot)
        {
            i++;
        }
        while (a[j] > pivot)
        {
            j--;
        }
        if ((i<Ipivot) && (j>Ipivot))
        {
            swap(a[i++], a[j--]);
        }
    }
    return Ipivot;
}
void quickSort(int a[], int start, int end)   //For Quick Sort
{
    if(start>=end)
        return;
    //partitioning of array
    int p=partition(a,start,end);
    //Sort left part
    quickSort(a,start,p-1);
    //Sort right part
    quickSort(a,p+1,end);
}

int main()
{
    int ch;
    cout<<"For Selection Sort: 1, Insertion Sort: 2, Quick Sort: 3."<<endl;
    cout<<"Enter your choice: ";
    cin>>ch;
    int n;
    cout<<"Enter the number of elements in the array: ";
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cout<<"Enter the element "<<i+1<<": ";
        cin>>a[i];
    }

    switch(ch)
    {
        case 1://Selection Sort
        {
            int min;
            for(int j=0;j<n-1;j++)
            {
                min=a[j];
                for(int k=j+1;k<n;k++)
                {
                    if(a[j]>a[k])
                    {
                        min=a[j];
                        a[j]=a[k];
                        a[k]=min;
                    }
                }
            }
            for(int l=0;l<n;l++)
            {
                cout<<a[l]<<" ";
            }
            break;
        }
        case 2://Insertion Sort
        {
            int min;
            for(int j=1;j<n;j++)
            {
                min=a[j];
                int k=j-1;
                while(a[k]>min && k>=0)
                {
                    a[k+1]=a[k];
                    k--;
                }
                a[k+1]=min;
            }
            for(int l=0;l<n;l++)
            {
                cout<<a[l]<<" ";
            }
            break;
        }
        case 3://Quick Sort
        {
            quickSort(a,0,n-1);
            for(int i=0;i<n;i++)
            {
                cout<<a[i]<<" ";
            }    
            break;
        }
        default:
        {
            cout<<"Enter correct choice."<<endl;
	    break;
        }
    }
}

4. Write function that translates a text to Pig Latin and back. English is translated to Pig Latin by taking the first letter of every word, moving it to the end of the word and adding ‘ay’. “The quick brown fox” becomes “Hetay uickqay rownbay oxfay”.
Solution :
def piglatin(sentence)
    sentence_array = sentence.split(" ") #split converts a sentence containing strings to 
    transformed_words = sentence_array.map do |word| #don't use .each or only the first item(i.e. word) will be returned
        first_letter = word.slice!(0) #removing first letter and storing in variable
        pig_word = word+first_letter+"ay"
    end
    transformed_words.join(" ") #.join will combine the strings in the array
end

puts piglatin("The quick brown fox")

# b - translate back

def english(sentence)
    sentence_array = sentence.split(" ")
    transformed_words = sentence_array.map do |word| #looping through each word in the array
        word = word.delete_suffix("ay") #deleting ay from the word
        first_letter = word.slice!(-1)     #  removing the last letter and assigning it as the first letter
        english_word = first_letter + word #joining first letter to the rest of the word
        english_word.capitalize
    end
     puts transformed_words.join(" ")
end

 english("Hetay uickqay rownbay oxfay")

5. Write a program that outputs all possibilities to put + or - or nothing between the numbers 1,2,…,9 (in this order) such that the result is 100. For example 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
Solution :
import re

array = [[0, 0, 0, 0, 0, 0, 0, 0]]
elems = [0, 0, 0, 0, 0, 0, 0, 0]

for n in range(6560):
    copy = elems.copy()
    copy[-1] += 1
    while 3 in copy:
        i = copy.index(3)
        copy[i:] = [0] * (len(copy) - i)
        copy[i - 1] += 1
    array.append(copy)
    elems = copy

lines = []

Fillers = ('+', '-', '')

j = 0

while len(lines) < 6561:
    expression = ''
    i, k = 0, 0
    for n in range(17):
        if n % 2 == 0:
            i += 1
            expression += str(i)
        else:
            expression += Fillers[array[j][k]]
            k += 1
    lines.append(expression)
    j += 1

lines.remove('123456789')

result = []

for line in lines:
    array = re.split('(\-|\+)', line)
    ops = 'add'
    num = 0
    for a in array:
        if a.isdigit():
            if ops == 'add':
                num += int(a)
            else:
                num  -= int(a)
        elif a in Fillers:
            if a == '+':
                ops = 'add'
            else:
                ops = 'sub'
    if num == 100: result.append(line)
    
result.sort()

print(*result, sep='\n')

6. Sort array of 0s,1s and 2s in a single scan (Visiting each element once).
Solution : 
#CPP
// Function to sort the input array,
void sort012(int a[])
{
	int n=arr.size();
	int low = 0;
	int high = n - 1;
	int mid = 0;

	// Iterate till all the elements
	// are sorted
	while (mid <= high) {
		switch (a[mid]) {

		// If the element is 0
		case 0:
			swap(a[low++], a[mid++]);
			break;

		// If the element is 1 .
		case 1:
			mid++;
			break;

		// If the element is 2
		case 2:
			swap(a[mid], a[high--]);
			break;
		}
	}
}

#Python
def sort_arr(a):
	n=len(a)
   	zero=0
	two=n-1
	sorted_list=[1 for x in range(n)]
	for i in range(n):
		if a[i]==0:
			sorted_list[zero]=0
			zero+=1
		elif a[i]==2:
			sorted_list[two]=2
			two-=1
		else:
			pass
	return sorted_list


7. The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
      I/O -> n = 4   O/P -> [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Solution : 
#CPP
//Used BackTraking Using Recursion
void sol(int ind,int n,vector<vector<int>> &v,map<int,int> &row,vector<int> &ds,vector<vector<int>> &flag)
    {
        if(ind==n)
        {
            v.push_back(ds);
            return;
        }
             
        
        for(int i=0;i<n;i++)
        {
            if(row[i]==0 && flag[i][ind]==0)
            { 
                for(int j=ind,k=i;j<n && k<n;k++,j++)
                 {
                   flag[k][j]++;
                }
                for(int j=ind,k=i;j<n && k>-1;k--,j++)
                 {
                   flag[k][j]++;
                }
                row[i]++;
                ds.push_back(i);
                sol(ind+1,n,v,row,ds,flag);
                ds.pop_back();
                for(int j=ind,k=i;j<n && k<n;k++,j++)
                 {
                   flag[k][j]--;
                }
                for(int j=ind,k=i;j<n && k>-1;k--,j++)
                 {
                   flag[k][j]--;
                }
                row[i]--;
            }   
        }
        return;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<int>> v;
        map<int,int> row;
        vector<int> ds;
        vector<vector<int>> flag(n,vector<int> (n,0));
        sol(0,n,v,row,ds,flag);
        vector<vector<string>> ans;
        vector<string> s;

        for(int i=0;i<v.size();i++)
        {
            for(int j=0;j<n;j++)
            {
                string temp;
                for(int k=0;k<n;k++)
                {
                    if(v[i][k]==j)
                        temp.append(1,'Q');
                    else 
                        temp.append(1,'.');
                }
                s.push_back(temp);
                
            }
            ans.push_back(s);
            s.clear();
        }
        
        
        return ans;
        
        
    }

8. Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list.
Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria:
  It must be greater than the original word
  It must be the smallest word that meets the first condition
      I/O -> abcd   O/P -> abdc  
      
Solution :#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);

string biggerIsGreater(string w) {
    int target = -1;
    int target2 = -1;
    for(int i=w.size()-1;i>=0;i--){
        if(w[i]-'a'>w[i-1]-'a'){
            target = i-1;
            break;
        }
    }
    if(target==-1){
        return "no answer";
    }
    for(int i=w.size()-1;i>=0;i--){
        if(w[i]-'a'>w[target]-'a'){
            target2=i;
            break;
        }
    }
    swap(w[target],w[target2]);
    reverse(w.begin()+target+1,w.end());
    return w;
}   
int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string T_temp;
    getline(cin, T_temp);

    int T = stoi(ltrim(rtrim(T_temp)));

    for (int T_itr = 0; T_itr < T; T_itr++) {
        string w;
        getline(cin, w);

        string result = biggerIsGreater(w);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

9.Given an array A[] consisting of only 0s, 1s, and 2s. The task is to write a function that sorts the given array. The functions should put all 0s first, then all 1s and all 2s in last.[dutch flag algorithm.]

solution:
#Python

def sort012(arr):
    low = 0
    high = len(arr) - 1
    mid = 0
    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low = low + 1
            mid = mid + 1
        elif arr[mid] == 1:
            mid = mid + 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high = high - 1
    return arr
    
//cpp
#include <bits/stdc++.h>
using namespace std;
 
void sort012(int a[], int arr_size)
{
    int lo = 0;
    int hi = arr_size - 1;
    int mid = 0;
 
    while (mid <= hi) {
        switch (a[mid]) {
 
        case 0:
            swap(a[lo++], a[mid++]);
            break;
 
        case 1:
            mid++;
            break;
 
        case 2:
            swap(a[mid], a[hi--]);
            break;
        }
    }
}

void printArray(int arr[], int arr_size)
{
    // Iterate and print every element
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << " ";
}
 
int main()
{
    int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    sort012(arr, n);
 
    printArray(arr, n);
 
    return 0;
}

10)Write a C++ program to rearrange the elements of a given array of integers in zig-zag fashion way.
Solution:
#include<iostream>
using namespace std;
 
void zig_zag_array(int nums[], int n)
{
    bool ans = true;
 
    for (int i=0; i<=n-2; i++)
    {
        if (ans) 
        {
            if (nums[i] > nums[i+1])
                swap(nums[i], nums[i+1]);
        }
        else  
        {
            if (nums[i] < nums[i+1])
                swap(nums[i], nums[i+1]);
        }
        ans = !ans; 
    }
}
 
int main()
{
    int nums[] = {0, 1, 3, 4, 5, 6, 7, 8, 10};
    int n = sizeof(nums)/sizeof(nums[0]);
   	cout << "Original array: ";
    for (int i=0; i < n; i++) 
    cout << nums[i] <<" ";
    zig_zag_array(nums, n);
    cout << "\nNew array elements: ";
    for (int i=0; i < n; i++) 
      cout << nums[i] <<" ";
  return 0;     
}

11) Write a python program for finding Median of Two Sorted Arrays.
Solution:
//Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
//The overall run time complexity should be O(log (m+n)).

import math
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums3=nums1+nums2
        nums3.sort()
        if len(nums3)%2==0:
            
            return float((nums3[len(nums3)/2]+nums3[len(nums3)/2-1]))/2
        else:
            return nums3[int(math.ceil(len(nums3)/2))]

12)Merge the two linked lists in a one sorted list. 
Solution:
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
            // if list1 happen to be NULL
            // we will simply return list2.
            if(l1 == NULL)
            {
                return l2;
            }
            
            // if list2 happen to be NULL
            // we will simply return list1.
            if(l2 == NULL)
            {
                return l1;
            } 
            
            // if value pointend by l1 pointer is less than equal to value pointed by l2 pointer
            // we wall call recursively l1 -> next and whole l2 list.
            if(l1 -> val <= l2 -> val)
            {
                l1 -> next = mergeTwoLists(l1 -> next, l2);
                return l1;
            }
            // we will call recursive l1 whole list and l2 -> next
            else
            {
                l2 -> next = mergeTwoLists(l1, l2 -> next);
                return l2;            
            }
        }
    };	

13.Calulate the Maximum sum of Even-Odd Subarray
Solution:
//----------------------Maximum Even Odd subarray Length---------------
#include<iostream>
#include<algorithm>
using namespace std;

//-----------------------------approach 1:O(n2)--------------------------
//int evenodd(int a[],int n)
//{
//    int res=1;
//    for(int i=0;i<n;i++)
//    {
//        int curr=1;
//        for(int j=i+1;j<n;j++)
//        {
//            if ( (a[j]%2==0 && a[j-1]%2!=0) || (a[j-1]%2==0 && a[j]%2!=0) )
//            curr++;
//            else
//            break;
//            
//        }
//        res=max(res,curr);
//
//    }
//    return res;
//
//}

//--------------------------approach 2: SUBARRAY technique------------------

int evenodd(int a[],int n)
{
    int res=1,curr=1;

    for(int i=1;i<n;i++)
    {
        if( (a[i]%2==0 && a[i-1]%2!=0) || (a[i-1]%2==0 && a[i]%2!=0))
        {curr++;
         res=max(res,curr);
        }
        else
        curr=1; 
    }
    return res;
    
}
int main()
{  
     int a[100],n;
    cout<<" Enter the size of array :";
    cin>>n;

    cout<<"\n enter the elemnts of an array one by one:";
    for(int i=0;i<n;i++)
    cin>>a[i];

    int len=evenodd(a,n);
    cout<<endl<<len;
    return 0;

}

15.(Word Ladder)
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Solution:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        if(find(wordList.begin(),wordList.end(),endWord)==wordList.end())
            return 0;
        set<string> s;
        for(auto i:wordList)
            s.insert(i);
        queue<string> q;
        q.push(beginWord);
        int d=0;
        while(!q.empty())
        {
            d++;
            int n=q.size();
            while(n--)
            {
                string curr=q.front();
                q.pop();
                for(int i=0;i<curr.length();i++)
                {
                    string tmp=curr;
                    for(char c='a';c<='z';c++)
                    {
                        tmp[i]=c;
                        if(tmp==curr)
                            continue;
                        if(tmp==endWord)
                            return d+1;
                        if(s.find(tmp)!=s.end())
                        {
                            q.push(tmp);
                            s.erase(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

14. Write a program to Implement Bubble Sort (Iterative) in a LinkedList

Solution :
//cpp

//Solution.cpp
int len(Node* head)
{
    Node* temp = head ;
    int i = 0 ;
     while(temp!=NULL)
     {
         i++;
         temp=temp->next ;
     }
    
    return i ;
}
Node *bubbleSort(Node *head)
{
    if(head == NULL)
        return head;
    int n = len(head)-1;
  
   while(n--)

   {
       Node* prev =NULL;
    Node*cur = head;
    while(cur->next!=NULL)
    {
        if(cur->data >=cur->next->data)
        {
            
             if(prev==NULL)
            {
                //first node
                Node* nxt = cur->next ;
                cur->next = nxt->next ;
                nxt->next = cur ;
               prev=nxt ;
                head = prev ;                
            }
            
            else
            {   
                 Node* nxt = cur->next ;
                prev->next = nxt ;
                cur->next = nxt->next ;
                nxt->next = cur ;
                prev = nxt ;
            }
            
        }

        else
        {        
          prev = cur ; 
          cur=cur->next ;
        }
        
    }
       
   }
      
    return head ;

}

// main.cpp

#include <iostream>
class Node
{
public:
	int data;
	Node *next;
	Node(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};

using namespace std;
#include "solution.h"
Node *takeinput()
{
	int data;
	cin >> data;
	Node *head = NULL, *tail = NULL;
	while (data != -1)
	{
		Node *newnode = new Node(data);
		if (head == NULL)
		{
			head = newnode;
			tail = newnode;
		}
		else
		{
			tail->next = newnode;
			tail = newnode;
		}
		cin >> data;
	}
	return head;
}
void print(Node *head)
{
	Node *temp = head;
	while (temp != NULL)
	{
		cout << temp->data << " ";
		temp = temp->next;
	}
	cout << endl;
}
int main()
{
	Node *head = takeinput();
	head = bubbleSort(head);
	print(head);
}

16) An array consist of n elements.Given an integer k.
    Write a program to find the sum of the lengths of the sub-arrays with k as its       maximum number. Any two sub-arrays that are considered should not overlap each       other. Find the maximum possible sum.
    
solution:  -----python-----

	 def Solve(n,k,a):
	    res =0
	    i=0
	    while(i<n) :
		ncnt=0
		bcheck = False
		while i<n and a[i] <= k:
		    ncnt= ncnt + 1
		    if a[i] == k:
			bcheck = True
		    i = i+ 1

		if bcheck =  True:
		    res = res + ncnt

		while i<n and a[i] > k:
		    i = i+ 1

	    return res
	    

	T = int(intput())
	for _ in range(T):

	    n,k = map(int , intpu().split())

	    a= list(map(int,intput().split()))

	    out_ = Solve(n,k,a)

	    print (out_)