ladka6/code_dataset
03
1query,lang1,lang2
2Level order traversal with direction change after every two levels,"/*JAVA program to print Zig-Zag traversal3in groups of size 2.*/4 5import java.util.*;6class GFG7{8static final int LEFT = 0;9static final int RIGHT = 1;10static int ChangeDirection(int Dir)11{12Dir = 1 - Dir;13return Dir;14}15/*A Binary Tree Node*/16 17static class node18{19 int data;20 node left, right;21};22/*Utility function to create a new tree node*/23 24static node newNode(int data)25{26 node temp = new node();27 temp.data = data;28 temp.left = temp.right = null;29 return temp;30}31/* Function to print the level order of32 given binary tree. Direction of printing33 level order traversal of binary tree changes34 after every two levels */35 36static void modifiedLevelOrder(node root)37{38 if (root == null)39 return ; 40 int dir = LEFT;41 node temp;42 Queue <node > Q = new LinkedList<>();43 Stack <node > S = new Stack<>();44 S.add(root);45/* Run this while loop till queue got empty*/46 47 while (!Q.isEmpty() || !S.isEmpty())48 {49 while (!S.isEmpty())50 {51 temp = S.peek();52 S.pop();53 System.out.print(temp.data + "" "");54 if (dir == LEFT)55 {56 if (temp.left != null)57 Q.add(temp.left);58 if (temp.right != null)59 Q.add(temp.right);60 }61 /* For printing nodes from right to left,62 push the nodes to stack63 instead of printing them.*/64 65 else {66 if (temp.right != null)67 Q.add(temp.right);68 if (temp.left != null)69 Q.add(temp.left);70 }71 } 72 System.out.println();73/* for printing the nodes in order74 from right to left*/75 76 while (!Q.isEmpty())77 {78 temp = Q.peek();79 Q.remove();80 System.out.print(temp.data + "" "");81 if (dir == LEFT) {82 if (temp.left != null)83 S.add(temp.left);84 if (temp.right != null)85 S.add(temp.right);86 } else {87 if (temp.right != null)88 S.add(temp.right);89 if (temp.left != null)90 S.add(temp.left);91 }92 }93 System.out.println();94/* Change the direction of traversal.*/95 96 dir = ChangeDirection(dir);97 }98}99/*Driver code*/100 101public static void main(String[] args)102{103/* Let us create binary tree*/104 105 node root = newNode(1);106 root.left = newNode(2);107 root.right = newNode(3);108 root.left.left = newNode(4);109 root.left.right = newNode(5);110 root.right.left = newNode(6);111 root.right.right = newNode(7);112 root.left.left.left = newNode(8);113 root.left.left.right = newNode(9);114 root.left.right.left = newNode(3);115 root.left.right.right = newNode(1);116 root.right.left.left = newNode(4);117 root.right.left.right = newNode(2);118 root.right.right.left = newNode(7);119 root.right.right.right = newNode(2);120 root.left.right.left.left = newNode(16);121 root.left.right.left.right = newNode(17);122 root.right.left.right.left = newNode(18);123 root.right.right.left.right = newNode(19);124 modifiedLevelOrder(root);125}126}",127Smallest of three integers without comparison operators,"/*Java implementation of above approach*/128 129class GFG130{131static int CHAR_BIT = 8;132/*Function to find minimum of x and y*/133 134static int min(int x, int y)135{136 return y + ((x - y) & ((x - y) >>137 ((Integer.SIZE/8) * CHAR_BIT - 1)));138}139/*Function to find minimum of 3 numbers x, y and z*/140 141static int smallest(int x, int y, int z)142{143 return Math.min(x, Math.min(y, z));144}145/*Driver code*/146 147public static void main (String[] args)148{149 int x = 12, y = 15, z = 5;150 System.out.println(""Minimum of 3 numbers is "" +151 smallest(x, y, z));152}153}"," '''Python3 implementation of above approach'''154 155CHAR_BIT = 8156 '''Function to find minimum of x and y'''157 158def min(x, y):159 return y + ((x - y) & \160 ((x - y) >> (32 * CHAR_BIT - 1)))161 '''Function to find minimum162of 3 numbers x, y and z'''163 164def smallest(x, y, z):165 return min(x, min(y, z))166 '''Driver code'''167 168x = 12169y = 15170z = 5171print(""Minimum of 3 numbers is "",172 smallest(x, y, z))"173Count pairs from two sorted arrays whose sum is equal to a given value x,"/*Java implementation to count174pairs from both sorted arrays175whose sum is equal to a given176value*/177 178import java.io.*;179class GFG {180/* function to count all pairs181 from both the sorted arrays182 whose sum is equal to a given183 value*/184 185 static int countPairs(int arr1[],186 int arr2[], int m, int n, int x)187 {188 int count = 0;189 int l = 0, r = n - 1;190/* traverse 'arr1[]' from191 left to right192 traverse 'arr2[]' from193 right to left*/194 195 while (l < m && r >= 0)196 {197/* if this sum is equal198 to 'x', then increment 'l',199 decrement 'r' and200 increment 'count'*/201 202 if ((arr1[l] + arr2[r]) == x)203 {204 l++; r--;205 count++; 206 }207/* if this sum is less208 than x, then increment l*/209 210 else if ((arr1[l] + arr2[r]) < x)211 l++;212/* else decrement 'r'*/213 214 else215 r--;216 }217/* required count of pairs*/218 219 return count;220 }221/* Driver Code*/222 223 public static void main (String[] args)224 {225 int arr1[] = {1, 3, 5, 7};226 int arr2[] = {2, 3, 5, 8};227 int m = arr1.length;228 int n = arr2.length;229 int x = 10;230 System.out.println( ""Count = ""231 + countPairs(arr1, arr2, m, n, x));232 }233}"," '''Python 3 implementation to count234pairs from both sorted arrays235whose sum is equal to a given236value'''237 238 '''function to count all pairs239from both the sorted arrays240whose sum is equal to a given241value'''242 243def countPairs(arr1, arr2, m, n, x):244 count, l, r = 0, 0, n - 1 ''' traverse 'arr1[]' from245 left to right246 traverse 'arr2[]' from247 right to left'''248 249 while (l < m and r >= 0):250 ''' if this sum is equal251 to 'x', then increment 'l',252 decrement 'r' and253 increment 'count'''254 '''255 if ((arr1[l] + arr2[r]) == x):256 l += 1257 r -= 1258 count += 1259 ''' if this sum is less260 than x, then increment l'''261 262 elif ((arr1[l] + arr2[r]) < x):263 l += 1264 ''' else decrement 'r'''265 '''266 else:267 r -= 1268 ''' required count of pairs'''269 270 return count271 '''Driver Code'''272 273if __name__ == '__main__':274 arr1 = [1, 3, 5, 7]275 arr2 = [2, 3, 5, 8]276 m = len(arr1)277 n = len(arr2)278 x = 10279 print(""Count ="",280 countPairs(arr1, arr2,281 m, n, x))"282Interpolation Search,"/*Java program to implement interpolation283search with recursion*/284 285import java.util.*;286class GFG {287/* If x is present in arr[0..n-1], then returns288 index of it, else returns -1.*/289 290 public static int interpolationSearch(int arr[], int lo,291 int hi, int x)292 {293 int pos;294/* Since array is sorted, an element295 present in array must be in range296 defined by corner*/297 298 if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {299/* Probing the position with keeping300 uniform distribution in mind.*/301 302 pos = lo303 + (((hi - lo) / (arr[hi] - arr[lo]))304 * (x - arr[lo]));305/* Condition of target found*/306 307 if (arr[pos] == x)308 return pos;309/* If x is larger, x is in right sub array*/310 311 if (arr[pos] < x)312 return interpolationSearch(arr, pos + 1, hi,313 x);314/* If x is smaller, x is in left sub array*/315 316 if (arr[pos] > x)317 return interpolationSearch(arr, lo, pos - 1,318 x);319 }320 return -1;321 }322/* Driver Code*/323 324 public static void main(String[] args)325 {326/* Array of items on which search will327 be conducted.*/328 329 int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,330 22, 23, 24, 33, 35, 42, 47 };331 int n = arr.length;332/* Element to be searched*/333 334 int x = 18;335 int index = interpolationSearch(arr, 0, n - 1, x);336/* If element was found*/337 338 if (index != -1)339 System.out.println(""Element found at index ""340 + index);341 else342 System.out.println(""Element not found."");343 }344}"," '''Python3 program to implement345interpolation search346with recursion'''347 348 '''If x is present in arr[0..n-1], then349returns index of it, else returns -1.'''350 351def interpolationSearch(arr, lo, hi, x): ''' Since array is sorted, an element present352 in array must be in range defined by corner'''353 354 if (lo <= hi and x >= arr[lo] and x <= arr[hi]):355 ''' Probing the position with keeping356 uniform distribution in mind.'''357 358 pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) *359 (x - arr[lo]))360 ''' Condition of target found'''361 362 if arr[pos] == x:363 return pos364 ''' If x is larger, x is in right subarray'''365 366 if arr[pos] < x:367 return interpolationSearch(arr, pos + 1,368 hi, x)369 ''' If x is smaller, x is in left subarray'''370 371 if arr[pos] > x:372 return interpolationSearch(arr, lo,373 pos - 1, x)374 return -1375 '''Driver code'''376 '''Array of items in which377search will be conducted'''378 379arr = [10, 12, 13, 16, 18, 19, 20,380 21, 22, 23, 24, 33, 35, 42, 47]381n = len(arr)382 '''Element to be searched'''383 384x = 18385index = interpolationSearch(arr, 0, n - 1, x)386 ''' If element was found'''387 388if index != -1:389 print(""Element found at index"", index)390else:391 print(""Element not found"")"392Check whether Matrix T is a result of one or more 90° rotations of Matrix mat,,393Program to find whether a no is power of two,"/*Java program to efficiently394check for power for 2*/395 396class Test397{398 /* Method to check if x is power of 2*/399 400 static boolean isPowerOfTwo (int x)401 {402 /* First x in the below expression is403 for the case when x is 0 */404 405 return x!=0 && ((x&(x-1)) == 0);406 }407/* Driver method*/408 409 public static void main(String[] args)410 {411 System.out.println(isPowerOfTwo(31) ? ""Yes"" : ""No"");412 System.out.println(isPowerOfTwo(64) ? ""Yes"" : ""No"");413 }414}"," '''Python program to check if given415number is power of 2 or not'''416 417 '''Function to check if x is power of 2'''418 419def isPowerOfTwo (x): ''' First x in the below expression420 is for the case when x is 0'''421 422 return (x and (not(x & (x - 1))) )423 '''Driver code'''424 425if(isPowerOfTwo(31)):426 print('Yes')427else:428 print('No')429if(isPowerOfTwo(64)):430 print('Yes')431else:432 print('No')"433Leaders in an array,"/*Java Function to print leaders in an array */434 435class LeadersInArray436{437 void printLeaders(int arr[], int size)438 {439 for (int i = 0; i < size; i++)440 {441 int j;442 for (j = i + 1; j < size; j++)443 {444 if (arr[i] <=arr[j])445 break;446 }/*the loop didn't break*/447 448if (j == size) 449 System.out.print(arr[i] + "" "");450 }451 }452 /* Driver program to test above functions */453 454 public static void main(String[] args)455 {456 LeadersInArray lead = new LeadersInArray();457 int arr[] = new int[]{16, 17, 4, 3, 5, 2};458 int n = arr.length;459 lead.printLeaders(arr, n);460 }461}"," '''Python Function to print leaders in array'''462 463def printLeaders(arr,size):464 for i in range(0, size):465 for j in range(i+1, size):466 if arr[i]<=arr[j]:467 break468 '''If loop didn't break'''469 470 if j == size-1: 471 print arr[i],472 '''Driver function'''473 474arr=[16, 17, 4, 3, 5, 2]475printLeaders(arr, len(arr))"476Convert an Array to a Circular Doubly Linked List,"/*Java program to convert array to477circular doubly linked list*/478 479class GFG480{481 482/*Doubly linked list node*/483 484static class node485{486 int data;487 node next;488 node prev;489};490 491/*Utility function to create a node in memory*/492 493static node getNode()494{495 return new node();496}497 498/*Function to display the list*/499 500static int displayList( node temp)501{502 node t = temp;503 if(temp == null)504 return 0;505 else506 {507 System.out.print(""The list is: "");508 509 while(temp.next != t)510 {511 System.out.print(temp.data+"" "");512 temp = temp.next;513 }514 515 System.out.print(temp.data);516 517 return 1;518 }519}520 521/*Function to convert array into list*/522 523static node createList(int arr[], int n, node start)524{525/* Declare newNode and temporary pointer*/526 527 node newNode,temp;528 int i;529 530/* Iterate the loop until array length*/531 532 for(i = 0; i < n; i++)533 {534/* Create new node*/535 536 newNode = getNode();537 538/* Assign the array data*/539 540 newNode.data = arr[i];541 542/* If it is first element543 Put that node prev and next as start544 as it is circular*/545 546 if(i == 0)547 {548 start = newNode;549 newNode.prev = start;550 newNode.next = start;551 }552 else553 {554/* Find the last node*/555 556 temp = (start).prev;557 558/* Add the last node to make them559 in circular fashion*/560 561 temp.next = newNode;562 newNode.next = start;563 newNode.prev = temp;564 temp = start;565 temp.prev = newNode;566 }567 }568 return start;569}570 571/*Driver Code*/572 573public static void main(String args[])574{575/* Array to be converted*/576 577 int arr[] = {1,2,3,4,5};578 int n = arr.length;579 580/* Start Pointer*/581 582 node start = null;583 584/* Create the List*/585 586 start = createList(arr, n, start);587 588/* Display the list*/589 590 displayList(start);591}592}593 594 595"," '''Python3 program to convert array to596circular doubly linked list'''597 598 599 '''Node of the doubly linked list'''600 601class Node:602 603 def __init__(self, data):604 self.data = data605 self.prev = None606 self.next = None607 608 '''Utility function to create a node in memory'''609 610def getNode():611 612 return (Node(0))613 614 '''Function to display the list'''615 616def displayList(temp):617 618 t = temp619 if(temp == None):620 return 0621 else:622 623 print(""The list is: "", end = "" "")624 625 while(temp.next != t):626 627 print(temp.data, end = "" "")628 temp = temp.next629 630 print(temp.data)631 632 return 1633 634 '''Function to convert array into list'''635 636def createList(arr, n, start):637 638 ''' Declare newNode and temporary pointer'''639 640 newNode = None641 temp = None642 i = 0643 644 ''' Iterate the loop until array length'''645 646 while(i < n):647 648 ''' Create new node'''649 650 newNode = getNode()651 652 ''' Assign the array data'''653 654 newNode.data = arr[i]655 656 ''' If it is first element657 Put that node prev and next as start658 as it is circular'''659 660 if(i == 0):661 662 start = newNode663 newNode.prev = start664 newNode.next = start665 666 else:667 668 ''' Find the last node'''669 670 temp = (start).prev671 672 ''' Add the last node to make them673 in circular fashion'''674 675 temp.next = newNode676 newNode.next = start677 newNode.prev = temp678 temp = start679 temp.prev = newNode680 i = i + 1681 return start682 683 '''Driver Code'''684 685if __name__ == ""__main__"":686 687 ''' Array to be converted'''688 689 arr = [1, 2, 3, 4, 5]690 n = len(arr)691 692 ''' Start Pointer'''693 694 start = None695 696 ''' Create the List'''697 698 start = createList(arr, n, start)699 700 ''' Display the list'''701 702 displayList(start)703 704 705"706Deepest left leaf node in a binary tree,"/*A Java program to find707the deepest left leaf708in a binary tree*/709 710/*A Binary Tree node*/711 712class Node713{714 int data;715 Node left, right;/* Constructor*/716 717 public Node(int data)718 {719 this.data = data;720 left = right = null;721 }722}723/*Class to evaluate pass724by reference */725 726class Level 727{728/* maxlevel: gives the729 value of level of730 maximum left leaf*/731 732 int maxlevel = 0;733}734class BinaryTree 735{736 Node root;737/* Node to store resultant738 node after left traversal*/739 740 Node result;741/* A utility function to742 find deepest leaf node.743 lvl: level of current node.744 isLeft: A bool indicate745 that this node is left child*/746 747 void deepestLeftLeafUtil(Node node, 748 int lvl, 749 Level level,750 boolean isLeft) 751 {752/* Base case*/753 754 if (node == null) 755 return;756/* Update result if this node757 is left leaf and its level758 is more than the maxl level759 of the current result*/760 761 if (isLeft != false &&762 node.left == null &&763 node.right == null &&764 lvl > level.maxlevel)765 {766 result = node;767 level.maxlevel = lvl;768 }769/* Recur for left and right subtrees*/770 771 deepestLeftLeafUtil(node.left, lvl + 1,772 level, true);773 deepestLeftLeafUtil(node.right, lvl + 1,774 level, false);775 }776/* A wrapper over deepestLeftLeafUtil().*/777 778 void deepestLeftLeaf(Node node) 779 {780 Level level = new Level();781 deepestLeftLeafUtil(node, 0, level, false);782 }783/* Driver program to test above functions*/784 785 public static void main(String[] args) 786 {787 BinaryTree tree = new BinaryTree();788 tree.root = new Node(1);789 tree.root.left = new Node(2);790 tree.root.right = new Node(3);791 tree.root.left.left = new Node(4);792 tree.root.right.left = new Node(5);793 tree.root.right.right = new Node(6);794 tree.root.right.left.right = new Node(7);795 tree.root.right.right.right = new Node(8);796 tree.root.right.left.right.left = new Node(9);797 tree.root.right.right.right.right = new Node(10);798 tree.deepestLeftLeaf(tree.root);799 if (tree.result != null)800 System.out.println(""The deepest left child""+801 "" is "" + tree.result.data);802 else803 System.out.println(""There is no left leaf in""+804 "" the given tree"");805 }806}"," '''Python program to find the deepest left leaf in a given807Binary tree'''808 '''A binary tree node'''809 810class Node:811 ''' Constructor to create a new node'''812 813 def __init__(self, val):814 self.val = val 815 self.left = None816 self.right = None817 '''A utility function to find deepest leaf node.818lvl: level of current node.819maxlvl: pointer to the deepest left leaf node found so far820isLeft: A bool indicate that this node is left child821of its parent822resPtr: Pointer to the result'''823 824def deepestLeftLeafUtil(root, lvl, maxlvl, isLeft):825 ''' Base CAse'''826 827 if root is None:828 return829 ''' Update result if this node is left leaf and its 830 level is more than the max level of the current result'''831 832 if(isLeft is True):833 if (root.left == None and root.right == None):834 if lvl > maxlvl[0] : 835 deepestLeftLeafUtil.resPtr = root 836 maxlvl[0] = lvl 837 return838 ''' Recur for left and right subtrees'''839 840 deepestLeftLeafUtil(root.left, lvl+1, maxlvl, True)841 deepestLeftLeafUtil(root.right, lvl+1, maxlvl, False)842 '''A wrapper for left and right subtree'''843 844def deepestLeftLeaf(root):845 maxlvl = [0]846 deepestLeftLeafUtil.resPtr = None847 deepestLeftLeafUtil(root, 0, maxlvl, False)848 return deepestLeftLeafUtil.resPtr849 '''Driver program to test above function'''850 851root = Node(1)852root.left = Node(2)853root.right = Node(3)854root.left.left = Node(4)855root.right.left = Node(5)856root.right.right = Node(6)857root.right.left.right = Node(7)858root.right.right.right = Node(8)859root.right.left.right.left = Node(9)860root.right.right.right.right= Node(10)861result = deepestLeftLeaf(root) 862if result is None:863 print ""There is not left leaf in the given tree""864else:865 print ""The deepst left child is"", result.val"866Print unique rows in a given boolean matrix,"/*Given a binary matrix of M X N867of integers, you need to return868only unique rows of binary array */869 870class GFG{871static int ROW = 4;872static int COL = 5;873/*Function that prints all874unique rows in a given matrix.*/875 876static void findUniqueRows(int M[][])877{878/* Traverse through the matrix*/879 880 for(int i = 0; i < ROW; i++)881 {882 int flag = 0;883/* Check if there is similar column884 is already printed, i.e if i and885 jth column match.*/886 887 for(int j = 0; j < i; j++)888 {889 flag = 1;890 for(int k = 0; k < COL; k++)891 if (M[i][k] != M[j][k])892 flag = 0;893 if (flag == 1)894 break;895 }896/* If no row is similar*/897 898 if (flag == 0)899 {900/* Print the row*/901 902 for(int j = 0; j < COL; j++)903 System.out.print(M[i][j] + "" "");904 System.out.println();905 }906 }907}908/*Driver Code*/909 910public static void main(String[] args)911{912 int M[][] = { { 0, 1, 0, 0, 1 },913 { 1, 0, 1, 1, 0 },914 { 0, 1, 0, 0, 1 },915 { 1, 0, 1, 0, 0 } };916 findUniqueRows(M);917}918}"," '''Given a binary matrix of M X N of919integers, you need to return only920unique rows of binary array'''921 922ROW = 4923COL = 5924 '''The main function that prints925all unique rows in a given matrix.'''926 927def findUniqueRows(M):928 ''' Traverse through the matrix'''929 930 for i in range(ROW):931 flag = 0932 ''' Check if there is similar column933 is already printed, i.e if i and934 jth column match.'''935 936 for j in range(i):937 flag = 1938 for k in range(COL):939 if (M[i][k] != M[j][k]):940 flag = 0941 if (flag == 1):942 break943 ''' If no row is similar'''944 945 if (flag == 0):946 ''' Print the row'''947 948 for j in range(COL):949 print(M[i][j], end = "" "")950 print() 951 '''Driver Code'''952 953if __name__ == '__main__':954 M = [ [ 0, 1, 0, 0, 1 ],955 [ 1, 0, 1, 1, 0 ],956 [ 0, 1, 0, 0, 1 ],957 [ 1, 0, 1, 0, 0 ] ]958 findUniqueRows(M)"959Delete leaf nodes with value as x,"/*Java code to delete all leaves with given 960value. */961 962class GfG { 963/*A binary tree node */964 965static class Node { 966 int data; 967 Node left, right; 968}969/*A utility function to allocate a new node */970 971static Node newNode(int data) 972{ 973 Node newNode = new Node(); 974 newNode.data = data; 975 newNode.left = null;976 newNode.right = null; 977 return (newNode); 978} 979 980/*deleteleaves()*/981 982static Node deleteLeaves(Node root, int x) 983{ 984 if (root == null) 985 return null; 986 root.left = deleteLeaves(root.left, x); 987 root.right = deleteLeaves(root.right, x); 988 if (root.data == x && root.left == null && root.right == null) { 989 return null; 990 } 991 return root; 992} /*inorder()*/993 994static void inorder(Node root) 995{ 996 if (root == null) 997 return; 998 inorder(root.left); 999 System.out.print(root.data + "" ""); 1000 inorder(root.right); 1001} /*Driver program */1002 1003public static void main(String[] args) 1004{ 1005 Node root = newNode(10); 1006 root.left = newNode(3); 1007 root.right = newNode(10); 1008 root.left.left = newNode(3); 1009 root.left.right = newNode(1); 1010 root.right.right = newNode(3); 1011 root.right.right.left = newNode(3); 1012 root.right.right.right = newNode(3); 1013 deleteLeaves(root, 3); 1014 System.out.print(""Inorder traversal after deletion : ""); 1015 inorder(root); 1016}1017}"," '''Python3 code to delete all leaves 1018with given value. '''1019 1020 '''A utility class to allocate a new node '''1021 1022class newNode:1023 def __init__(self, data):1024 self.data = data 1025 self.left = self.right = None1026 '''deleteleaves()'''1027 1028def deleteLeaves(root, x):1029 if (root == None):1030 return None1031 root.left = deleteLeaves(root.left, x) 1032 root.right = deleteLeaves(root.right, x) 1033 if (root.data == x and 1034 root.left == None and 1035 root.right == None):1036 return None1037 return root '''inorder()'''1038 1039def inorder(root):1040 if (root == None): 1041 return1042 inorder(root.left) 1043 print(root.data, end = "" "") 1044 inorder(root.right) '''Driver Code'''1045 1046if __name__ == '__main__': 1047 root = newNode(10) 1048 root.left = newNode(3) 1049 root.right = newNode(10) 1050 root.left.left = newNode(3) 1051 root.left.right = newNode(1) 1052 root.right.right = newNode(3) 1053 root.right.right.left = newNode(3) 1054 root.right.right.right = newNode(3) 1055 deleteLeaves(root, 3) 1056 print(""Inorder traversal after deletion : "") 1057 inorder(root)"1058The Stock Span Problem,"/*Java linear time solution for stock span problem*/1059 1060import java.util.Stack;1061import java.util.Arrays;1062public class GFG {1063/* A stack based efficient method to calculate1064 stock span values*/1065 1066 static void calculateSpan(int price[], int n, int S[])1067 {1068/* Create a stack and push index of first element1069 to it*/1070 1071 Stack<Integer> st = new Stack<>();1072 st.push(0);1073/* Span value of first element is always 1*/1074 1075 S[0] = 1;1076/* Calculate span values for rest of the elements*/1077 1078 for (int i = 1; i < n; i++) {1079/* Pop elements from stack while stack is not1080 empty and top of stack is smaller than1081 price[i]*/1082 1083 while (!st.empty() && price[st.peek()] <= price[i])1084 st.pop();1085/* If stack becomes empty, then price[i] is1086 greater than all elements on left of it, i.e.,1087 price[0], price[1], ..price[i-1]. Else price[i]1088 is greater than elements after top of stack*/1089 1090 S[i] = (st.empty()) ? (i + 1) : (i - st.peek());1091/* Push this element to stack*/1092 1093 st.push(i);1094 }1095 }1096/* A utility function to print elements of array*/1097 1098 static void printArray(int arr[])1099 {1100 System.out.print(Arrays.toString(arr));1101 }1102/* Driver method*/1103 1104 public static void main(String[] args)1105 {1106 int price[] = { 10, 4, 5, 90, 120, 80 };1107 int n = price.length;1108 int S[] = new int[n];1109/* Fill the span values in array S[]*/1110 1111 calculateSpan(price, n, S);1112/* print the calculated span values*/1113 1114 printArray(S);1115 }1116}"," '''Python linear time solution for stock span problem1117 ''' '''A stack based efficient method to calculate s'''1118 1119def calculateSpan(price, S):1120 n = len(price)1121 ''' Create a stack and push index of fist element to it'''1122 1123 st = []1124 st.append(0)1125 ''' Span value of first element is always 1'''1126 1127 S[0] = 11128 ''' Calculate span values for rest of the elements'''1129 1130 for i in range(1, n):1131 ''' Pop elements from stack whlie stack is not1132 empty and top of stack is smaller than price[i]'''1133 1134 while( len(st) > 0 and price[st[-1]] <= price[i]):1135 st.pop()1136 ''' If stack becomes empty, then price[i] is greater1137 than all elements on left of it, i.e. price[0],1138 price[1], ..price[i-1]. Else the price[i] is1139 greater than elements after top of stack'''1140 1141 S[i] = i + 1 if len(st) <= 0 else (i - st[-1])1142 ''' Push this element to stack'''1143 1144 st.append(i)1145 '''A utility function to print elements of array'''1146 1147def printArray(arr, n):1148 for i in range(0, n):1149 print (arr[i], end ="" "")1150 '''Driver program to test above function'''1151 1152price = [10, 4, 5, 90, 120, 80]1153S = [0 for i in range(len(price)+1)]1154 '''Fill the span values in array S[]'''1155 1156calculateSpan(price, S)1157 '''Print the calculated span values'''1158 1159printArray(S, len(price))"1160Rotate a matrix by 90 degree in clockwise direction without using any extra space,"import java.io.*;1161 1162class GFG {1163 1164/*rotate function*/1165 1166 1167 static void rotate(int[][] arr)1168 {1169 1170 int n = arr.length;1171 /* first rotation1172 with respect to Secondary diagonal*/1173 1174 for (int i = 0; i < n; i++) {1175 for (int j = 0; j < n - i; j++) {1176 int temp = arr[i][j];1177 arr[i][j] = arr[n - 1 - j][n - 1 - i];1178 arr[n - 1 - j][n - 1 - i] = temp;1179 }1180 }1181/* Second rotation1182 with respect to middle row*/1183 1184 for (int i = 0; i < n / 2; i++) {1185 for (int j = 0; j < n; j++) {1186 int temp = arr[i][j];1187 arr[i][j] = arr[n - 1 - i][j];1188 arr[n - 1 - i][j] = temp;1189 }1190 }1191 }1192 1193/* to print matrix*/1194 1195 static void printMatrix(int arr[][])1196 {1197 int n = arr.length;1198 for (int i = 0; i < n; i++) {1199 for (int j = 0; j < n; j++)1200 System.out.print(arr[i][j] + "" "");