Module-03

.
Euclid’s Algorithm
• GCD can be found in two ways:
i. Traditional Method
ii. Euclid’s Algorithm

Traditional Method
Example : gcd (12,33)→?
Given Numbers 12 33
Divisors ----------------1,2,3,4,6,12 1,3,11,33
Common Divisors ----------------------- 1,3
Greatest Common Divisors-----------------3
Euclid Algorithm:
Example gcd(12,33)----->?
Max(12,33) will be given to a
quotient a b remainder
2 33 12 9
1 12 9 3
3 9 3 0
3 0

Stop the process as b is ‘0’ and whatever the ‘a’ contains that is the gcd
of the two numbers.
gcd(12,33)=3
1. import java.util.Scanner;
2. class Main{
3. public static int gcd(int a,int b)
4. {
5. if(b==0)
6. return a;
7. return gcd(b,a%b);
8. }
9. public static void main (String[] args) {
10. Scanner sc=new Scanner(System.in);
11. int n=sc.nextInt();
12. int m=sc.nextInt();
13. System.out.print(gcd(n,m));
14. }
15. }
Karatsuba Algorithm
• The Karatsuba algorithm is a fast multiplication algorithm that utilizes
a divide-and-conquer strategy to multiply two large numbers.

• Let's us consider x and y as two numbers then product of x and y is:

Steps:

1. Calculate ac

2. Calculate bd

3. Calculate (a+b)(c+d)-ac-bd

4. Substitute in main formulae.

Examples

1. 996632 x 12345

2. 71894 x 8656

3. 123 x 456

4. 5678 x 1234

5. 123456 x 987654

6. 314159 × 271828
1. public static long mul(long x,long y)
2. {
3. if(x<10 || y<10)
4. return x*y;
5. int len=(int)Math.max(String.valueOf(x).length(),String.valueOf(y).length());
6. int n=len/2;
7. long a=(long)(x/Math.pow(10,n));
8. long b=(long)(x%Math.pow(10,n));
9. long c=(long)(y/Math.pow(10,n));
10. long d=(long)(y%Math.pow(10,n));
11. long ac=mul(a,c);
12. long bd=mul(b,d);
13. long ab_cd=mul(a+b,c+d)-ac-bd;
14. long res=((ac*(long)Math.pow(10,2*n))+((ab_cd)*(long)Math.pow(10,n))+bd);
15. return res;
16. }
longest sequence of 1's in binary representation with one flip

• Give an integer n. We can flip exactly one bit. Write code to find the
length of the longest sequence of 1 s you could create.
Input : 1775

Output : 8

Binary representation of 1775 is 11011101111.

After flipping the highlighted bit, we get

consecutive 8 bits.
1. public static int longestSequence(int n) {
2. if (~n == 0)
3. return Integer.BYTES * 8;
4.
5. int currLen = 0;
6. int prevLen = 0;
7. int maxLen = 1;
8. while (n != 0) {
9. if ((n & 1) == 1) {
10. currLen++;
11. } else {
12. prevLen = ( (n & 2) == 0 ) ? 0 : currLen;
13. currLen = 0;
14. }
15. maxLen = Math.max(maxLen, prevLen + 1 + currLen);
16. n >>= 1;
17. }
18. return maxLen;
19. }
Swapping two nibbles in a byte

• A nibble = 4 bits.
A byte = 8 bits = 2 nibbles (high nibble + low nibble).
Steps
1. Isolate the lower nibble.(byte_value & 0x0F)

2. Shift the lower nibble to the left.(byte_value & 0x0F) << 4)

3. Isolate the higher nibble. (byte_value & 0xF0)

4. Shift the higher nibble to the right. (byte_value & 0xF0) >> 4

5. Combine the shifted nibbles.

((byte_value & 0x0F) << 4) | ((byte_value & 0xF0) >> 4)

1. import java.util.*;
2. public class Main {

3. public static int swap(int n)

4. {
5. return ((n&0x0f)<<4 | (n&0xf0)>>4);
6. }

7. public static void main(String[] args) {

8. Scanner sc = new Scanner(System.in);
9. int num = sc.nextInt();
10. System.out.println("Swapping two nibbles in a byte " + swap(num));
11. }
12. }
Move hyphen to the beginning of the String

• Write a program to move all hyphens ('-') in a given string to the

beginning of the string, while maintaining the relative order of the
other characters.
• Input:
Move-This-Hyphen

• Output:
--MoveThisHyphen
1. import java.util.*;
2. public class Main {
3. public static String movehyphen(String n) {
4. String s1="";
5. String s2="";
6. for(int i=0;i<n.length();i++)
7. {
8. if(n.charAt(i)=='-')
9. s1=s1+n.charAt(i);
10. else
11. s2=s2+n.charAt(i);
12. }
13. return (s1+s2);
14. }
15. public static void main(String[] args) {
16. Scanner sc = new Scanner(System.in);
17. String s = sc.next();
18. System.out.println("After Moving movehyphen to the beginning " + movehyphen(s));
19. }
20. }
Maximum sum of hour glass in matrix
• Given a 2D matrix, the task is to find the maximum sum of an hourglass.
• An hour glass is made of 7 cells in following form.
tuv
x
xyz
• Input :
• [[0, 3, 0, 0, 0],
[0, 1, 0, 0, 0],
[1, 1, 1, 0, 0],
[0, 0, 2, 4, 4],
[0, 0, 0, 2, 4]]
Output : 11
1. import java.util.*;
2. public class Main {
3. public static void main(String[] args) {
4. Scanner sc=new Scanner(System.in);
5. int r=sc.nextInt();
6. int c=sc.nextInt();
7. int a[][]=new int[r][c];
8. for(int i=0;i<r;i++) {
9. for(int j=0;j<c;j++) {
10. a[i][j]=sc.nextInt(); } }
11. int max_sum=Integer.MIN_VALUE;
12. for(int i=0;i<r-2;i++) {
13. int s=0;
14. for(int j=0;j<c-2;j++) {
15. s=s+a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2];
16. }
17. max_sum=Math.max(s,max_sum);
18. }
19. System.out.print(max_sum); }}
Leaders in an Array
• Given an integer array a[] of size n. write a program to find the leaders
in the array a[].

• Note: An element in an array is a leader if it is strictly greater than all

elements on its right side.
• Last element of any array will always be the leader.
• The largest element in the array is also always eligible to be a leader.
• Sample Input -- 1:
a[]=[16,17,4,3,5,2]
• Sample output: [2,5,17]

• Sample input – 2:
a[]=[6,5,4,3,2,1]
• Sample output: [1,2,3,4,5,6]
Approaches
• Brute force Approach:
The outer loop starts from 0 to n.
The inner loop starts from i+1 to n.
Comparing a[i] with all the a[j] elements if a[i] is greater than a[j] then
we will declare a[i] as the leader otherwise not a leader.

Time Complexity : O(n^2)

public static void findLeaders(int[] arr)
{
if (arr.length == 0) {
System.out.println("Array is empty.");
return;
}
for (int i = 0; i < arr.length; i++) {
boolean isLeader = true;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[i]) {
isLeader = false;
break;
}
}
if (isLeader) {
System.out.println("Leaders in the array: " + arr[i]);
}}}
Efficient Approach

• Take a max variable and initialize to Integer.MIN_VALUE then take a

single loop and compare a[i] with max value if a[i] > max value
declare a[i] as leader and change max value to a[i].

• Time Complexity: O(n)

public static void printLeaders(int[] arr)
{
int n = arr.length;
int max = Integer.MIN_VALUE;
for (int i = n - 1; i >= 0; i--)
{
if (arr[i] > max)
{
System.out.print(arr[i] + " ");
max = arr[i];
} }}
Majority Element in the array
• Write a program to find the majority element in the array.

Note: An element in an array is said to be a majority element if the

frequency of that element is greater than the half of the size of the array.
Sample Input-01

A[]=[2,23,4,4,5,5,4,4,4]

Sample output: 4 is the majority element in the given array

Sample input -02

A[]=[1,2,3,4,5,6,7,8]

Sample output: There is no majority element in the given array.

Brute Force Approach

1. int maxc=0,ind=-1; 10. if(c>maxc)

2. for(int i=0;i<n;i++) 11. {
3. { 12. maxc=c;
4. int c=0; 13. ind=i;
5. for(int j=0;j<n;j++) 14. } }
6. if(a[i]==a[j]) 15. if(maxc>n/2)
7. { 16. System.out.print(a[ind]);
8. c++; 17. else
9. } 18. System.out.print(-1);
Moore’s Voting Algorithm(Efficient Approach)
1. import java.util.*;
2. public class Main {
3. public static void main(String[] args) {
4. Scanner sc=new Scanner(System.in);
5. int n=sc.nextInt();
6. int a[]=new int[n];
7. for(int i=0;i<n;i++)
8. a[i]=sc.nextInt();
1. int maj_ind=0,c=1;
2. for(int i=0;i<n;i++) {
3. if(a[i]==a[maj_ind])
4. c++;
5. else {
6. c--;
7. if(c==0) {
8. c=1;
9. maj_ind=i;
10. } } }
11. c=0;
12. for(int i=0;i<n;i++) {
13. if(a[i]==a[maj_ind])
14. c++;
15. }
16. if(c>n/2)
17. System.out.print(a[maj_ind]);
18. else
19. System.out.print(-1);
20. }}
Maximum equilibrium sum in an array
Given an array arr[]. Find the maximum value of prefix sum which is also
suffix sum for index i in arr[].
Input
5
12321
Output : 2(index)

Input :
8
-3 5 3 1 2 6 -4 2
Output : -1
1. import java.util.*;
2. public class Main {
3. public static void main(String[] args) {
4. Scanner sc=new Scanner(System.in);
5. int n=sc.nextInt();
6. int a[]=new int[n];
7. int ts=0,l=0,ind=-1;
8. for(int i=0;i<n;i++) {
9. a[i]=sc.nextInt();
10. ts=ts+a[i];
11. }
12. int ms=Integer.MIN_VALUE;
13. for(int i=0;i<n;i++) {
14. ts=ts-a[i];
15. if(l==ts && l>ms) {
16. ms=l;
17. ind=i;
18. }
19. else
20. l=l+a[i];
21. }
22. System.out.print(ind);
23. }}
Max Product Subarray
• Given an array arr[] consisting of positive, negative, and zero values, find
the maximum product that can be obtained from any contiguous
subarray of arr[].
• Example 1:
• Input: nums = [2,3,-2,4]
• Output: 6

• Example 2:
• Input: nums = [-2,0,-1]
• Output: 0
1. import java.util.*; 11. for(int i=0;i<n;i++) {

2. public class Main { 12. if(pre_pro==0) pre_pro=1;

3. public static void main(String[] args) { 13. if(suff_pro==0) suff_pro=1;

4. Scanner sc=new Scanner(System.in); 14. pre_pro=pre_pro*a[i];

5. int n=sc.nextInt(); 15. suff_pro=suff_pro*a[n-i-1];

6. int a[]=new int[n]; 16. max_pro=Math.max(max_pro,Math.max(pre_pro,suff_pro));

7. for(int i=0;i<n;i++) 17. }

8. a[i]=sc.nextInt(); 18. System.out.println(max_pro);

9. int max_pro=Integer.MIN_VALUE; 19. }

10. int pre_pro=1,suff_pro=1; 20. }

Selection Sort

• This sorting is a in-place (it doesn’t take extra space for storing)
comparison based algorithm.

• Here the array is divided into two parts sorted and unsorted.

• Initially sorted part is empty and unsorted part is the entire array.

• The Smallest element from the unsorted array and swapped with the
leftmost element and then that element becomes the part of sorted.
Algorithm

• Step 1 − i loop location starts from 0 to n

• Step 2 −j loop location starts from i+1 to n

• Step 3 − if arr[j] < arr[i] take index into min_ind variable

• Step 4 − Swap(a[j],a[i])

• Step 5 − Repeat until list is sorted

Main Logic
1. public static void selectionSort(int[] arr) {
2. int n = arr.length;
3. for (int i = 0; i < n; i++) {
4. int minind=i;
5. for (int j = i + 1; j < n; j++) {
6. if (arr[j] < arr[minind]) {
7. minind=j;
8. }}
9. int temp = arr[minind];
10. arr[minind] = arr[j];
11. arr[j] = temp;
12. }
13. }
Quick Sort

• Follows Divide & Conquer Approach

• It picks an element as a pivot and partitions the given array around the
pivot.

• Pivot element can be any element(i.e 1st or last or middle element).

• Partitioning the array and sorting the array is the main concept of
quick sort.
Cont…

• The partition of the array should be such a way that all the elements
less than pivot should be left side of the pivot and all the elements
greater than pivot should be right side of the pivot.
• If pivot element is duplicate then that element can be shifted to
either of the side.
• -------------------------------------------------------------------
-------------------------------------------------------------------
elements less than pivot pivot elements greater than pivot
 Array Partition
public static int partition(int arr[], int lb, int ub) { if (start < end) {
int pivot = arr[lb]; int temp = arr[start];
int start = lb; arr[start] = arr[end];
int end = ub;
arr[end] = temp;
}
while (start < end) {
}
while (arr[start] <= pivot && start<ub) {
int temp = arr[lb];
start++;
arr[lb] = arr[end];
}
arr[end] = temp;
while (arr[end] > pivot) { return end;
end--; }
} }
Quicksort
public static void quicksort(int arr[], int lb, int ub) {
int loc;
if (lb < ub) {
loc = partition(arr, lb, ub);
quicksort(arr, lb, loc - 1);
quicksort(arr, loc + 1, ub);
}
}
 Weighted Substring
• Given a string P consisting of small English letters and a string Q consisting
of weight of all characters of English alphabet. The task is to find the total
numbers of unique substring with sum of weights atmost K.

Input: P = "acbacbacaa", Q = "12300045600078900012345000", K = 2

Output: 3
Explanation:
The substrings with the sum of weights of individual characters ? 2 are:
"a", "b", "aa"
• Input: P = "ababab", Q = "12345678912345678912345678", K = 5
Output: ?
1. import java.util.*;
21. public static boolean dup(String s[],String temp,int c){
2. public class Main {
3. static void main(String[] args) {
22. for(int i=0;i<c;i++){
4. Scanner sc=new Scanner(System.in); 23. if(s[i].equals(temp)) return true;
5. String p=sc.next(); 24. }
6. String q=sc.next(); 25. return false;
7. int k=sc.nextInt(); 26. }
8. int c=0,n=p.length(); 27. }
9. String s[]=new String[(n*(n+1))/2];
10. for(int i=0;i<n;i++){
11. StringBuilder sb=new StringBuilder();
12. int sum=0;
13. for(int j=i;j<n;j++){
14. sb.append(p.charAt(j));
15. int pos=p.charAt(j)-'a';
16. int w=q.charAt(pos)-'0';
17. sum=sum+w;
18. if(sum<=k && !dup(s,sb.toString(),c)){
19. s[c++]=sb.toString(); } } }
20. System.out.print(c); }
Block Swap Algorithm
• Given an array of n size, rotate the array by k elements using the Block
Swap Algorithm.

• Example 1:
• Input: N = 5, array[] = {1,2,3,4,5} K=2
• Output: {3,4,5,1,2}

• Example 2:
• Input: N = 7, array[] = {1,2,3,4,5,6,7} K=3
• Output: {4,5,6,7,1,2,3}
Algorithm
Initialize A = r and B = n-r
1) Do following until size of A is equal to size of B

a) If A is shorter, divide B into Bl and Br such that Br is of same

length as A. Swap A and reduce size of B as B-A.

b) If A is longer, divide A into Al and Ar such that Al is of same

length as B Swap Al and reduce size of A as A-B.

2) Finally, when A and B are of equal size, block swap them.

1. import java.util.*; 10. while(A!=B) {
2. public class Main 11. if(A<B) {
3. { 12. swap(a,r-A,r+B-A,A);
4. public static void main(String[] args) 13. B=B-A;
5. { 14. }
6. Scanner sc=new Scanner(System.in); 15. else{
7. int n=sc.nextInt(); 16. swap(a,r-A,r,B);
8. int a[]=new int[n]; 17. A=A-B;
9. for(int i=0;i<n;i++) 18. }}
10. a[i]=sc.nextInt(); 19. swap(a,r-A,r,A);
11. int r=sc.nextInt(); 20. for(int i=0;i<n;i++)
12. if(r==0||r==n) return; 21. System.out.print(a[i]+" ");
13. int A=r,B=n-r; 22. }
23. public static void swap(int a[],int st,int ed,int r)
24. {
25. for(int i=0;i<r;i++)
26. {
27. int temp=a[st+i];
28. a[st+i]=a[ed+i];
29. a[ed+i]=temp;
30. }
31. }
32. }//class closing