Intermediate.txt

Example : 
Solution :
# Python  
age=input(int("Age : "))
print(age);
                                                                                                                                               Maintainer : Gaurav-2803
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. Write a guessing game where the user has to guess a secret number. After every guess the program tells the user whether  their number was too large or too small. 
At the end the number of tries needed should be printed. It counts only as one try if they input the same number multiple times consecutively.
Solution : 

#Python
import getpass
print("THE GUESSING GAME!\n")
no = int(getpass.getpass("Enter any Number for Friend to Guess: "))
i = 1
while (True):
    temp = int(input("\nEnter Your Guess "))
    if temp == no:
        print("Correct Guess!")
        print("You WON!! \n")
        if i==1:
            print("You did it in", i, "Guess! Yay!")
        elif i>=2 and i<=4:
            print("You did it in only", i, "Guesses!")
        elif i>=5 and i<=8:
            print("You did it in", i, "Guesses!")
        else:
            print("You required", i,"Guesses :(")
        break
    elif temp<no:
        print("Your guess is Less!")
        print("Try Again. \n")
    else:
        print("Your guess is Large!")
        print("Try Again. \n")
    if i==1:
        prev_no=temp
        i+=1
    elif prev_no==temp:
        pass
    else:
        prev_no=temp
        i += 1
	
#CPP
//Solution Begins
#include<bits/stdc++.h>
#include<stdlib.h>
using namespace std;
void guess(int num){
    cout << "GUESS THE NUMBER!!\n\n";
    int i=1;
    int a=1;
    while (a){
        int temp;
        cout<<"\nEnter your guess : ";
        cin >> temp;
        if (temp==num){
            cout << "Correct Guess!\nYou WON!!\n";
            if (i==1){
                cout << "You did it in "<< i<< " Guess! Yay!";
            }
            else if (i>=2 && i<=4){
                cout <<"\nYou did it in only "<< i<< " Guesses!";
            }
            else if (i>=5 && i<=8)
                cout<<"\nYou did it in "<<i<<" Guesses!";
            else
                cout <<"\nYou required "<<i<<" Guesses :(";
            a=0;
        }
        else if (temp<num){
            cout << "Your guess is Less!\n";
            cout << "Try Again. \n";
        }
        else{
            cout << "Your guess is Large!\n";
            cout << "Try Again. \n";
        }
        int prev_no;
        if (i==1){
            prev_no=temp;
            i+=1;
        }
        else if (prev_no==temp){
            continue;
        }
        else{
            prev_no=temp;
            i += 1;
        }
    }
}
int main(){
    cout << "THE GAME BEGINS!!\n";
    cout << "Enter any Number for your friend to guess :- ";
    int b;
    cin >> b;
    system("clear");
    cout << "GAME IS ON!!\n\n";
    guess(b);

}


2. Write function that reverses a array, preferably in place.
Solution : 
#Python

def reverseArray(arr):
    start, end = 0, len(arr)-1
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1
        
#CPP

//Function
void reverse_array(vector<int> &arr)
{
   //Calculate size of array
   int n=arr.size();

   //loop will run till the mid position of given array
   for(int i=0;i<n/2;i++)
   {
      //swap elements
      swap(arr[i],arr[n-i-1]);
   }
   return;
}

#Java
static void reverseArray(int[] intArray,int size){
        int i, temp; 
        for (i = 0; i < size/ 2; i++) { 
            
            //store first index value at temp
            temp = intArray[i]; 
            
            //store lastIndex-i-1 value in i'th Index
            intArray[i] = intArray[size - i - 1]; 
            
            //store temp value at lastIndex-i-1 
            intArray[size - i - 1] = temp; 

            //Loop will run till the mid position of given array
        } 
        //printing the reversed Array
        System.out.println(Arrays.toString(intArray)); 
}
3. Write a function that tests whether a string is a palindrome.
Solution : 

class Solution {
    int isPalindrome(String S) {
      char [] ans=new char[S.length()];
      for(int i=0;i<S.length();i++){
          ans[i]=S.charAt(i);
      }
      int start=0;
      int end=S.length()-1;
      while(start<end){
          if(ans[start] != ans[end]){
              return 0;
          }
          start++;
          end--;
      }
      return 1;
    }
};
class Main{
public static void main(String[] args){
String str="abba";
String str1="";
StringBuilder ans=new StringBuilder();
ans.append(str);
ans.reverse;
str1=ans.toString();
if(str1==str){
System.out.print("Palindromic");
}
Systme.out.print("Not palindromic");
}
}

#CPP
class Solution{
public:	
	int isPalindrome(string S)
	{
	       int ch=0;
         string st;
         while(S[ch]!='\0'){
            st+=S[ch];
            ch++;
          }
          string newst;
          for(int i=ch-1;i>=0;i--){
          newst+=S[i];
          }
          if(newst==st){
            return 1;
          }
          return 0;
	}

};

#solved Q no 3 using python
#python
my_str =input("Enter string: ")
my_str = my_str.casefold()
rev_str = reversed(my_str)
if list(my_str) == list(rev_str):
   print("The string is a palindrome.")
else:
   print("The string is not a palindrome.")


4. Write a function that tests whether a number is a palindrome.
Solution : 
#Python
# Python program to check if number is Palindrome

def isPalindrome(n):  #user-defined function
	n=str(n)
	l=[]
	for i in n:
		l.append(i)
	rev_l=l[::-1]
	if l==rev_l:
		return 1
	else:
		return 0

# CPP
class Solution{
public:	
    int isPalindrome(int n) {
        int rev = 0;
        int temp = n;
        while(temp != 0) {
            int rem = temp % 10;
            rev = rev * 10 + rem;
            temp = temp / 10;
        }
        if(rev == n){
            return 1;
        }
        return 0;
    }
};


5. Write a function on_all that applies a function to every element of a list. Use it to print the first twenty perfect squares. The perfect squares can be found by multiplying each natural number with itself. The first few perfect squares are 1*1= 1, 2*2=4, 3*3=9, 4*4=16. Twelve for example is not a perfect square because there is no natural number m so that m*m=12.
Solution : 

6. Write a function that combines two arrays by alternatingly taking elements, e.g. [a,b,c], [1,2,3] → [a,1,b,2,c,3].
Solution : 
#CPP
vector<int> mergeArr(int arr1[],int arr2[],int m,int n){
	vector<int> ans(m+n);
	int a1=0;
	int a2=0;
	for(int i=0;i<(m+n);i++){
		if(i%2==0){
			ans.push_back(arr1[a1];
			a1++;
		}else{
			ans.push_back(arr2[a2]);
			a2++;
		}
	}
	return ans;
}

#Java

import java.util.Scanner;

public class Merge{

    static Scanner scanner = new Scanner(System.in);

    public static String[] merge(String[] list1, String[] list2){
        String[] pattern = new String[list1.length+list2.length];
        boolean flag = false;
        int count1 = 0, count2 = 0, count = 0;
        for (int i = 0; i < pattern.length; i++) {
            if (!flag){
                pattern[count] = list1[count1];
                count1++;
                count++;
                flag = true;
            }
            else {
                pattern[count] = list2[count2];
                count2++;
                count++;
                flag = false;
            }
        }
        return pattern;
    }

    public static void getData(String list[]){
        for (int i = 0; i < list.length; i++) {
            System.out.println("Enter element no. "+(i+1) +" : ");
            list[i] = scanner.next();
        }
    }

    public static void main(String[] args) {
        System.out.print("Enter the number of elements of list 1 :");
        int n1 = scanner.nextInt();
        String list1[] = new String[n1];
        getData(list1);
        System.out.print("Enter the number of elements of list 2 :");
        int n2 = scanner.nextInt();
        String list2[] = new String[n2];
        getData(list2);
        String[] merged = merge(list1,list2);
        for (int i = 0; i < merged.length; i++) {
            System.out.print(merged[i]+ " ");
        }
    }
}

7. Write a function that rotates a array by k elements. For example [1,2,3,4,5,6] rotated by two becomes [3,4,5,6,1,2]. Try solving this without creating a copy of the array. How many swap or move operations do you need?
Solution : 
//java
class Solution
{
    //Function to rotate an array by d elements in counter-clockwise direction. 
    static void rotateArr(int arr[], int d, int n)
    {
        int []ans=new int[n];
       int i=0;
       while(i<n-d){
           ans[i]=arr[i+d];
           i++;
       }
       int j=0;
       while(j<d){
           ans[i+j]=arr[j];
           j++;
       }
      
       for(int k=0;k<n;k++){
           arr[k]=ans[k];
       }
    }
}

 
class Main
{
    public static void rightRotateByOne(int[] A)
    {
        int last = A[A.length - 1];
        for (int i = A.length - 2; i >= 0; i--) {
            A[i + 1] = A[i];
        }
 
        A[0] = last;
    }
 
    public static void rightRotate(int[] A, int k)
    {
        if (k < 0 || k >= A.length) {
            return;
        }
 
        for (int i = 0; i < k; i++) {
            rightRotateByOne(A);
        }
    }
 
    public static void main(String[] args)
    {
        int[] A = { 1, 2, 3, 4, 5, 6, 7 };
        int k = 3;
 
        rightRotate(A, k);
 
        System.out.println(Arrays.toString(A));
    }
}

8. Write a function that takes a number and returns a array of its digits. So for 2342 it should return [2,3,4,2].
Solution : 
#CPP
	//Function
	vector<int> digit_to_vector(int n)
	{
	   //STL to convert Integer to String
	   string s=to_string(n);
	   vector<int> ans;
	   //Interating string
	   for(int i=0;i<s.size();i++)
	      ans.push_back(s[i]-'0'); 

	   return ans;
	}

#Java
  static void getDigit(int number){
        ArrayList<Integer> arr=new ArrayList<Integer>();
        // Printing the last digit of the number
        while (number > 0) {
            // Finding the remainder (Last Digit)
            int remainder = number % 10;
            // Printing the remainder/current last digit
            arr.add(remainder);
            // Removing the last digit/current last digit
            number = number / 10;
    }
    Collections.reverse(arr);
    System.out.println(arr);
}


9. Write functions that add, subtract, and multiply digits of two numbers.
Solution : 
#python

def add(a,b):
    return a+b;
def sub(a,b):
    return a-b;
def multiply(a,b):
    return a*b;

f1=add(5,5.2)
f2=sub(5,4.2)
f3=multiply(5,5.2)
print("Addition: ", f1)
print("substraction: ", f2)
print("multiplication: ", f3)


10. Implement binary search.
Solution : 
//java
class Solution {
    int binarysearch(int arr[], int n, int k){
        int start=0;
        int end=n-1;
        while(start<=end){
            int mid =start +(end-start)/2;
            if(arr[mid]<k){
                start=mid+1;
            }
            if(arr[mid]>k){
                end=mid-1;
            }
            if(arr[mid]==k) {
              return mid;
            }
        }
        return -1;
    }
}


=======
#Java
 class binarySearch {
  public int search(int[] nums, int target) {
    int key, start = 0, end = nums.length - 1;
    while (start <= end) {
      key = (start+end)/2  
      if (nums[key] == target){
        return key;
      } 
      if (target < nums[key]){
        end = key - 1;
     }
      else {
        left = key + 1;
        }
    }
    return -1;
  }
 public static void main(String args[]){  
        int arr[] = {10,20,30,40,50};  
        binarySearch(arr,30);     
 }   
}
def binary_search(list1, n):  
    low = 0  
    high = len(list1) - 1  
    mid = 0  
  
    while low <= high:  
        mid = (high + low) // 2  
        if list1[mid] < n:  
            low = mid + 1  
        elif list1[mid] > n:  
            high = mid - 1  
        else:  
            return mid  
    return -1  
 
# Initial list1  
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 45  
  
# Function call   
result = binary_search(list1, n)  
  
if result != -1:  
    print("Element is present at index", str(result))  
else:  
    print("Element is not present in list1") 



11. Write a function that takes a array of strings an prints them, one per line, in a rectangular frame. For example the list ["Hello", "World", "in", "a", "frame"] gets printed as:

*********
* Hello *
* World *
* in    *
* a     *
* frame *
*********

Solution : 
p=input("words?")

def frame(words):

    size = len(max(words, key=len))

    print('*' * (size + 4))

    for word in words:

        print(f'* {word} *')

    print('*' * (size + 4))

frame(p.split(" "))

12. Print the following pattern without using print in-built function.
i.      ii.     iii.    iv.
*       ***       *     ***
**      **       **      **
***     *       ***       *
v.      vi.     vii.    viii.
1       123       1     123
23      45       23      45
456     5       456       6

Solution : 
// i)
void printPat(int n)
{
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j<=i){
                cout<<"*"<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

// ii)
void printPat(int n)
{
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j<=(n/2-i-1)){
                cout<<"*"<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

// iii)
void printPat(int n)
{
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j>=(n/2-i-1)){
                cout<<"*"<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

// iv)
void printPat(int n)
{
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j>=i){
                cout<<"*"<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

//v)
void printPat(int n)
{
    int count=1;
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j<=i){
                cout<<count++<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

// vi)
void printPat(int n)
{
    int count=1;
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j<=(n/2-i-1)){
                cout<<count++<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

// vii)
void printPat(int n)
{
    int count=1;
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j>=(n/2-i-1)){
                cout<<count++<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

// viii)
void printPat(int n)
{
    int count=1;
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(j>=i){
                cout<<count++<<" ";
            }else{
                cout<<"  ";
            }
        }
        cout<<"\n";
    }
}

13. Convert Age -> Days (Consider leap years in between) take year of birth as input also.
Solution : 
#python
from datetime import datetime, timedelta
my_DOB = datetime(2002, 4, 30)
todays_date = datetime.today()
age_in_days = todays_date - my_DOB
print("The age in days and time for the Given DOB = ", age_in_days)


14. 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.
Solution : // 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;
}

15. Write a function that takes number K where is smaller than size of array, we need to find the Kth smallest and largest elementin the given array.It is given that all array elements are not distinct and If not present return -1. 
Solution : 
//cpp
int findnum(int arr[],int n){
int k;
cin>>k;
if(k>=n)
return -1;
sort(arr,arr+n);
cout<<arr[k-1];
cout<<arr[n-k];
return 0;
}

16. Write a function that sort array of 0s, 1s & 2s (inbuilt sort functions are not allowed)
Solution : # Python program to sort an array with
# 0, 1 and 2 in a single pass
 
# Function to sort array
 
 
def sort012(a, arr_size):
    lo = 0
    hi = arr_size - 1
    mid = 0
    # Iterate till all the elements
    # are sorted
    while mid <= hi:
        # If the element is 0
        if a[mid] == 0:
            a[lo], a[mid] = a[mid], a[lo]
            lo = lo + 1
            mid = mid + 1
        # If the element is 1
        elif a[mid] == 1:
            mid = mid + 1
        # If the element is 2
        else:
            a[mid], a[hi] = a[hi], a[mid]
            hi = hi - 1
    return a
 
# Function to print array
 
 
def printArray(a):
    for k in a:
        print(k, end=' ')
 
 
# Driver Program
arr = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
arr_size = len(arr)
arr = sort012(arr, arr_size)
printArray(arr)

17. Given Unsorted array check whether elements are in Arithmetic Progression (Differnce between every 2 consecutive is same) if not return -1.
Example : 1,2,3,4,5 are in A.P
Solution : 
#Python
class Solution:
    
    def checkIsAP(self, arr, n):
        arr.sort()
        diff=arr[1]-arr[0]
        for i in range(2,n):
            if(arr[i]-arr[i-1]!=diff):
                return 0
        return 1
        
//cpp
int ap(int arr[],int n){
sort(arr,arr+n);
int d=arr[1]-arr[0];
for(int i=1;i<n;i++){
if(arr[i]-arr[i-1])!=d){
return -1;
}
}
return 1;
}


18. Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity.
Solution : 
#Python
def binarySearch(arr, low, high, k):
	while low <= high:
		mid = low + (high - low) // 2
		if arr[mid] == k:
			return mid
		elif arr[mid] < k:
			low = mid + 1
		else:
			high = mid - 1
	return low

//java
 int binarysearch(int arr[], int n, int k) {
        int start=0;
        int end=n-1;
        int ans=0;
        while(start<=end){
            int mid =start +(end-start)/2;
            if(arr[mid]<k){
                start=mid+1;
            }
            if(arr[mid]>k){
                end=mid-1;
            }
            if(arr[mid]==k) {
              return mid;
            }
            ans=mid;
        }
        return ans+1;
    }
    
    
#CPP
class Solution{
public:
    int binarysearch(int arr[], int n, int k){
        int first=0;
        int last=n-1;
        if(arr[0]>k){
            return 0;
        }
        int mid=(first+last)/2;
        while(first<last){
            if(arr[mid]==k){
                return mid;
            }
            if(arr[first]==k){
                return first;
            }
            if(arr[last]==k){
                return last;
            }
            if(k<arr[mid]){
                last=mid-1;
                mid=(first+last)/2;
            }else{
                first=mid+1;
                mid=(first+last)/2;
            }
        }
        return mid+1;
    }
};

19. Given a string S,of length N that is indexed from 0 to N-1, print its even-indexed and odd-indexed characters as 2 space-separated strings on a single line.
    I/P -> Gaurav   O/P -> Gua arv
Solution : 
class Main{
public static void main(String[] args){
String s="SlamanBhaijaan"
String ans="";
for(int i=0; i<s.length(); i++){
if(i%2==0){
ans=ans+s.charAt(i);
}
}
ans=ans+" ";
for(int i=0; i<s.length(); i++){
if(i%2!=0){
ans=ans+s.charAt(i);
}
}
return ans;
}

solution;
#python
n=int(input("enter the length of string"))
s=input("enter the string")
eve=[]
odd=[]
result=[]
for i in range (0,n):
    if i%2==0:
        eve.append(s[i])
    else:
        
        odd.append(s[i])
d=' '.join(eve)
e=' '.join(odd)
result.append(d)
result.append(e)
print(' '.join(result))



20 .Sort an array of 0s, 1s and 2s (Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order.)
/// java 
class Solution
{
    public static void sort012(int arr[], int n)
    {
        // code here 
        int zero =0;
        int one =0;
        int two =0;
        for(int i =0; i<n;i++){
            if (arr[i]==0){
                zero++;
            }
            else if(arr[i]==1){
                one++;
            }
            else{
                two++ ;
                
            }
        }
        for(int i=0;i<n;i++){
            if (zero>0){
                arr[i]=0;
                zero--;
            }
            else if(one>0){
                arr[i]=1;
                one--;
            }
            else{
                arr[i]=2;
            }
        }
    }
}

21. Remove duplicates in small prime array
Solution : 
class Solution
{
    ArrayList<Integer> removeDuplicate(int arr[], int n)
    {
        // code here 
        ArrayList<Integer>a=new ArrayList<>();
        for(int i=0;i<arr.length;i++){
            if(!a.contains(arr[i])){
                a.add(arr[i]);
            }
        }
        return a;
        
        
    }
}

22. Print all permutation of String both iterative and Recursive way?
Solution : 
#CPP
//Using Recursion//
void permute(string str, int l, int r) 
{ 
    // Base case 
    if (l == r) 
        cout<< str <<endl; 
    else
    { 
        // Permutations made 
        for (int i = l; i <= r; i++) 
        { 
  
            // Swapping done 
            swap(str[l], str[i]); 
  
            // Recursion called 
            permute(str, l+1, r); 
  
            //backtrack 
            swap(str[l], str[i]); 
        } 
    } 
} 

//Using Iteration//
// Function to print permutations of string str
// using next_permutation()
// Using STL
void permute(string str)
{
    // Sort the string in lexicographically
    // ascending order
    sort(str.begin(), str.end());
 
    // Keep printing next permutation while there
    // is next permutation
    do {
       cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));
}
 

23. Given two arrays, 1,2,3,4,5 and 2,3,1,0,5 find which number is not present in the second array.
Solution :
//cpp
int check(int arr[],int str[],int n){
int  ans=-1;
sort(arr,arr+n);
sort(str,str+n);
for(int i=0;i<n;i++){
if(arr[i]!=str[i]){
ans=arr[i];
break;
}
}
return ans;
}

#Python
def remain(arr,arr1):
    for i in arr:
        cnt=0
        for j in range(0,len(arr1)):
            if i==arr1[j]:
                cnt+=1
        if cnt==0:
            print(i)
            
arr=[1,2,3,4,5]
arr1=[2,3,1,0,5]
remain(arr,arr1)

24. In an array 1-100 multiple numbers are duplicates, find them?
Solution :
//function:-
public List<Integer> duplicate(int[] arr){
Arrays.sort(arr);
List<Integer> ans=new ArrayList<>();
for(int i=0; i<arr.length-1; i++){
if(arr[i]==arr[i+1]){
ans.add(arr[i]);
}
}
return ans;
}

25.Design a simple calculator using java.
solution:
// Java program for simple calculator
  
import java.io.*;
import java.lang.*;
import java.lang.Math;
import java.util.Scanner;
public class BasicCalculator {
  
    public static void main(String[] args)
    {
        // stores two numbers
        double num1, num2;
  
        // Take input from the user
        Scanner sc = new Scanner(System.in);
  
        System.out.println("Enter the numbers");
  
        // take the inputs
        num1 = sc.nextDouble();
  
        num2 = sc.nextDouble();
  
        System.out.println("Enter the operator (+,-,*,/)");
  
        char op = sc.next().charAt(0);
  
        double o = 0;
  
        switch (op) {
  
        // case to add two numbers
        case '+':
  
            o = num1 + num2;
  
            break;
  
        // case to subtract two numbers
        case '-':
  
            o = num1 - num2;
  
            break;
  
        // case to multiply two numbers
        case '*':
  
            o = num1 * num2;
  
            break;
  
        // case to divide two numbers
        case '/':
  
            o = num1 / num2;
  
            break;
  
        default:
  
            System.out.println("You enter wrong input");
  
            break;
        }
  
        System.out.println("The final result:");
  
        System.out.println();
  
        // print the final result
        System.out.println(num1 + " " + op + " " + num2
                           + " = " + o);
    }
}
26.Printing Butterfly pattern
Example For N=6:
*          *
**        **
***      ***
****    ****
*****  *****
************
************
*****  *****
****    ****
***      ***
**        **
*          *
Solution:
======================================
#Python

def butterflyPattern(N):
	for i in range(1, N + 1):
		for j in range(1, 2 * N + 1):
			if (i < j):
				print("", end = " ")
			else:
				print("*", end = "")
			if (i <= ((2 * N) - j)):
				print("", end = " ")
			else:
				print("*", end = "")
		print("")
	for i in range(1, N + 1):
		for j in range(1, 2 * N + 1):
			if (i > (N - j + 1)):
				print("", end = " ")
			else:
				print("*", end = "")
			if ((i + N) > j):
				print("", end = " ")
			else:
				print("*", end = "")
		print("")

#CPP

#include<iostream>
#include<stdlib.h>
#include <bits/stdc++.h>
#define ll long long int
#define fastio  cin.tie(0), cout.tie(0),ios_base::sync_with_stdio(false);

using namespace std;

int main() {
    fastio;
int b=1,i,j;
int N;
cin>>N;


for(i=1;i<=N;i++)
{

        for(j=1;j<=i;j++)
        cout<<"*";
       int  space=2*(N-i);
        for(j=1;j<=space;j++)
        cout<<" ";
        for(j=1;j<=i;j++)
        cout<<"*";

        cout<<endl;
}
for(i=N;i>=1;i--)
{
    for(j=1;j<=i;j++)
    cout<<"*";
    int space=2*(N-i);
    for(j=1;j<=space;j++)
    cout<<" ";
    for(j=1;j<=i;j++)
    cout<<"*";

    cout<<endl;
}

    return 0;
}

27. The number diamond pattern is a diamond pattern made up of numbers.
Solution :
//Cpp
#include <iostream>
using namespace std;

int main() {
  int size = 5;
  int num = 1;
  // upside pyramid
  for (int i = 1; i <= size; i++) {
    // printing spaces
    for (int j = size; j > i; j--) {
      cout << " ";
    }
    // printing number
    for (int k = 0; k < i * 2 - 1; k++) {
      cout << num++;
    }
    // set the number to 1
    num = 1;
    cout << "\n";
  }
  // downside pyramid
  for (int i = 1; i <= size - 1; i++) {
    // printing spaces
    for (int j = 0; j < i; j++) {
      cout << " ";
    }
    // printing number
    for (int k = (size - i) * 2 - 1; k > 0; k--) {
      cout << num++;
    }
    // set num to 1
    num = 1;
    cout << "\n";
  }
  return 0;
}


28. You have two coin piles containing a and b coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.
Your task is to efficiently find out if you can empty both the piles.

solution:
//cpp

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
void solve() {
    
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    ll a,b;
    cin>>a>>b;
 
    if((a+b)%3==0 && 2*b>=a && 2*a>=b)
    {
        cout<<"YES"<<"\n";
    }
    else{
        cout<<"NO"<<"\n";
    }
}
 
int main(){
    
    int t;
    cin>>t;
    while (t--){
    
        solve();
        
    }
    return 0;
}

29. Your task is to calculate the number of bit strings of length n.
    For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.
    Print the result modulo 109+7.
    
solution:
//cpp
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
 
int main(){
    
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    long long n, s=1;
    cin>>n;
    for (int i = 0; i < n; i++)
    {
        s=(s*2)%mod;
    }
    cout<<s;
    return 0;
}

30. Write a Java program to find the sum of even numbers in an integer array.

solution:
//java 

import java.util.Scanner;
public class Sum_Even_Array {
   public static void main(String args[]) {
   Scanner sc=new Scanner(System.in);
   int arr[]=new int[10],n=10;
   System.out.println("Enter 10 values");
         for(int i=0;i<n;i++)
         {
            arr[i]=sc.nextInt();
         }
   int sum=0, avg;
   for(int i=0;i<n;i++)
  {
     if(arr[i]%2==0)
     sum+=arr[i];
  }
   System.out.println("Sum of even ="+sum);
}
}

31. write a Java Program To Rotate A Linked List.

Problem Link : https://leetcode.com/problems/rotate-list/

Java Solution :

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        
        ListNode lencount = head;
        int Len = 0, y = 0;
        
        // To Get Length Of LL;
        do {
            ++Len;
            lencount = lencount.next;
        } while (lencount != null);
        
        
        // If Length And Rotation Count Are Same, So After K Rotations It Same As Original List;
        
        if (k == Len) {
            return head;
        }
       
        
        // Rotation Module;
        int rotate = Len - k % Len;
        
    
        // To Store Values Of LL;       
        int[] arr = new int[Len];
        ListNode CurHead = head;
        
        while (CurHead != null) {
            arr[y++] = CurHead.val;
            CurHead = CurHead.next;
        }
        
        // Resultant List;
        ListNode runner = head;

        
        for (int i = 0; i < arr.length; i++) {
            runner.val = arr[(i + rotate) % Len];
            runner = runner.next;
        }
        return head;
    }
}

32. Given an array arr[] of size N. The task is to find the sum of the contiguous subarray within a arr[] with the largest sum. 

Solution :

// cpp

#include <bits/stdc++.h>
#define int long long
#define INF 1000000000000000000
#define MOD 1000000009;
#define mid(l, u) ((l + u) / 2)
#define rchild(i) (i * 2 + 2)
#define lchild(i) (i * 2 + 1)
using namespace std;

signed main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int dp[n];
    dp[0] = a[0];
    int ans = a[0];
    for (int i = 1; i < n; i++)
        ans = max(ans, (dp[i] = a[i] + max(dp[i - 1], (int)0)));
    cout << ans << endl;
}

/*
Sample Input:
8
-2 -3 4 -1 -2 1 5 -3
Sample Output:
7
*/

33. Write a cpp program to merge k sorted list using both recursive and iterative approach

Problem Link : https://leetcode.com/problems/merge-k-sorted-lists/

Solution :

// cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
   public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        //// Iterative Approach
        //         ListNode *start = new ListNode();
        //         ListNode *tmp = start;

        //         while(l1 && l2) {
        //             if(l1->val < l2->val) {
        //                 tmp->next = l1;
        //                 l1 = l1->next;
        //             } else {
        //                 tmp->next = l2;
        //                 l2 = l2->next;
        //             }
        //             tmp = tmp->next;
        //         }
        //         if(l1) tmp->next = l1;
        //         if(l2) tmp->next = l2;
        //         return start->next;

        // Recursive Approach
        if (!l1) return l2;
        if (!l2) return l1;
        ListNode* head = l1->val <= l2->val ? l1 : l2;
        head->next = l1->val <= l2->val ? merge(l1->next, l2) : merge(l1, l2->next);
        return head;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return NULL;

        ListNode* head = lists[0];

        for (int i = 1; i < lists.size(); i++) {
            head = merge(head, lists[i]);
        }
        return head;
    }
};



34. Write a cpp program to Remove a leaf Node in Binary Tree

Solution :

// cpp

/**********************************************************
	Binary Tree Node class structure

	template <typename T>
	class BinaryTreeNode {
    	public : 
    	T data;
    	BinaryTreeNode<T> *left;
    	BinaryTreeNode<T> *right;

    	BinaryTreeNode(T data) {
        	this -> data = data;
        	left = NULL;
        	right = NULL;
    	}
	};

***********************************************************/
//Solution.cpp File
BinaryTreeNode<int>* removeLeafNodes(BinaryTreeNode<int> *root) {
    if(root == NULL)
        return NULL;
    if(root -> left == NULL && root->right== NULL){
        delete root;
        return NULL;
    }
    root -> left = removeLeafNodes(root->left);
    root -> right  = removeLeafNodes(root->right);
    return root;
        
}
//main.cpp
#include <iostream>
#include <queue>

template <typename T>
class BinaryTreeNode {
   public:
    T data;
    BinaryTreeNode<T>* left;
    BinaryTreeNode<T>* right;

    BinaryTreeNode(T data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

using namespace std;
#include "solution.cpp"

BinaryTreeNode<int>* takeInput() {
    int rootData;
    cin >> rootData;
    if (rootData == -1) {
        return NULL;
    }
    BinaryTreeNode<int>* root = new BinaryTreeNode<int>(rootData);
    queue<BinaryTreeNode<int>*> q;
    q.push(root);
    while (!q.empty()) {
        BinaryTreeNode<int>* currentNode = q.front();
        q.pop();
        int leftChild, rightChild;

        cin >> leftChild;
        if (leftChild != -1) {
            BinaryTreeNode<int>* leftNode = new BinaryTreeNode<int>(leftChild);
            currentNode->left = leftNode;
            q.push(leftNode);
        }

        cin >> rightChild;
        if (rightChild != -1) {
            BinaryTreeNode<int>* rightNode =
                new BinaryTreeNode<int>(rightChild);
            currentNode->right = rightNode;
            q.push(rightNode);
        }
    }
    return root;
}

void printLevelATNewLine(BinaryTreeNode<int>* root) {
    queue<BinaryTreeNode<int>*> q;
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
        BinaryTreeNode<int>* first = q.front();
        q.pop();
        if (first == NULL) {
            if (q.empty()) {
                break;
            }
            cout << endl;
            q.push(NULL);
            continue;
        }
        cout << first->data << " ";
        if (first->left != NULL) {
            q.push(first->left);
        }
        if (first->right != NULL) {
            q.push(first->right);
        }
    }
}

int main() {
    BinaryTreeNode<int>* root = takeInput();
    root = removeLeafNodes(root);
    printLevelATNewLine(root);
}


35. Write a function for Binary Tree Level Order Traversal

Solution :

// cpp

vector<vector<int>> levelOrder(TreeNode* root) {
	if(root == NULL){
	    return {};
	}
	 vector<vector<int>>ans;
	queue<TreeNode*>pending;
	TreeNode *temp = NULL;
	pending.push(root);
	int length;
	while(!pending.empty()){
	    length = pending.size();
	    vector<int>v;
	    for(int i=0;i<length;i++)
	    {
		temp = pending.front();
		pending.pop();
		v.push_back(temp->val);
		if(temp->left !=NULL){
		    pending.push(temp->left);
		}
		 if(temp->right !=NULL){
		    pending.push(temp->right);
		}
	    }
	    ans.push_back(v);
	}
	return ans;
36. Two Sum
Solution:
         vector<int> twoSum(vector<int>& nums, int target) {
    int len = nums.size();
    for(int i = 0; i < len; i++) {
        for(int j = i + 1; j < len; j++) {
            if(nums[j] == target - nums[i])
                return { i, j };
        }
    }
    return {-1, -1};
};
    
}

37. Implement merge sort.
solution:
#java

public class MergeSort {

	public static void main(String[] args) {

		int[] arr = { 70, 50, 30, 10, 20, 40, 60 };

		int[] merged = mergeSort(arr, 0, arr.length - 1);

		for (int val : merged) {
			System.out.print(val + " ");
		}

	}

	public static int[] mergeTwoSortedArrays(int[] one, int[] two) {

		int[] sorted = new int[one.length + two.length];

		int i = 0;
		int j = 0;
		int k = 0;

		while (i < one.length && j < two.length) {

			if (one[i] < two[j]) {
				sorted[k] = one[i];
				k++;
				i++;
			} else {
				sorted[k] = two[j];
				k++;
				j++;
			}
		}

		if (i == one.length) {

			while (j < two.length) {
				sorted[k] = two[j];
				k++;
				j++;
			}
		}

		if (j == two.length) {

			while (i < one.length) {
				sorted[k] = one[i];
				k++;
				i++;
			}
		}

		return sorted;

	}

	public static int[] mergeSort(int[] arr, int lo, int hi) {

		if (lo == hi) {
			int[] br = new int[1];
			br[0] = arr[lo];

			return br;
		}

		int mid = (lo + hi) / 2;

		int[] fh = mergeSort(arr, lo, mid);
		int[] sh = mergeSort(arr, mid + 1, hi);

		int[] merged = mergeTwoSortedArrays(fh, sh);

		return merged;
	}

}

38. Find First and Last Position of Element in Sorted Array

Problem Link: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Solution:
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int i = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int j = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (i < nums.size() && nums[i] == target) 
            return {i, j - 1};
        return {-1, -1};

    }

//     vector<int> searchRange(vector<int>& nums, int target) {
//         int idx1 = lower_bound(nums, target);
//         int idx2 = lower_bound(nums, target+1)-1;
//         if (idx1 < nums.size() && nums[idx1] == target)
//             return {idx1, idx2};
//         else
//             return {-1, -1};
//     }

//     int lower_bound(vector<int>& nums, int target) {
//         int l = 0, r = nums.size()-1;
//         while (l <= r) {
//             int mid = (r-l)/2+l;
//             if (nums[mid] < target)
//                 l = mid+1;
//             else
//                 r = mid-1;
//         }
//         return l;
//     }
};