### Problem -11 Addition of 2 Array Elements

Given is 2 Array e.g int first [] = {2,1,3,4} e.g int second [] = {4,2,4,5} So addition of first and second array is {6,3,7,9}

if we see the above case , we need to maintain ith pointer on first array which is placed at i = first.length-1, and jth on second array which is placed at j = second.length-1 and kth on third array which is placed at k = third.length-1. So the logic seems like third[k] = first[i] + second[j]

In the above image , this show a case of carry. If you do a sum and you get the carry, so like 9 +5 =14 and we want 4 and 1 become carry so simply if we do 14%10 so we get 4 and 14/10 so we get the carry. The Default value of carry is 0 if it has so update it. Finally the equation will be e.g third[k] = first[i] + second[i] + carry. Now the question arise , if the carry left at end so first we print the carry and then the value of the third array.

In the above case if one of the array is bigger, in this case we create third array based on the size of the bigger array.

```
int first [] = {9,1,8,9,2};
int second[] = {9,1,2,7};
int third [] = new int [first.length>second.length?first.length:second.length];
```

Full Source Code ðŸ‘‡

```
public class SumOfArray {
public static void main(String[] args) {
int first [] = {9,1,8,9,2};
int second[] = {9,1,2,7};
int third [] = new int [first.length>second.length?first.length:second.length];
int carry = 0;
int sum = 0 ;
int i = first.length - 1;
int j = second.length -1 ;
int k = third.length -1;
while(k>=0){
if(i>=0 && j>=0){
sum = first[i] + second[j] + carry;
}
else
if(i>=0 && j<0){
sum = first[i] + carry;
}
else
if(j>=0 && i<0){
sum = second[j] + carry;
}
carry = sum/10;
sum = sum % 10;
third[k] = sum;
i--;
j--;
k--;
}
if(carry!=0){
System.out.print(carry);
}
for(int ele : third){
System.out.print(ele);
}
System.out.println();
}
}
```

### Problem-12 Subtraction of 2 Array

Given is 2 Array e.g int first [] = {5,1,3,4} e.g int second [] = {4,2,4,5} So Subraction of first and second array is {8,8,9}. Note : Assume first array is always greater than the second one. so the third array always is same length of first one.

If we find out the first value is less than the second one so we add 10 to the value and carry -1 and then do the subtraction with the second value.

In this case we carry till before 0th index and keep adding 10 whenever we take carry and when reach to the 0th index just add the carry not add 10. Â

Full Source Code ðŸ‘‡

```
public class SubtractionOfTwoArray12 {
public static void main(String[] args) {
int first [] = {5,1 ,3,4};
//int first [] = {1,0,0,0,0};
int second [] = {2,4,5};
// int second[] = {4,2,4,5};
//int second[] = {9};
// given is first array is greater than second one
int third [] = new int[first.length];
int i = first.length-1;
int j = second.length-1;
int k = third.length-1;
int carry = 0;
int diff = 0;
while(k>=0){
if(j>=0){
if(first[i]<second[j]){
diff = first[i] + 10 + carry - second[j] ;
carry = -1;
}
else{
diff = first[i] + carry - second[j];
carry = 0;
}
}
else{
if(i>=1 && carry==-1){
diff = first[i] + 10 + carry;
}
else{
diff = first[i] + carry ;
}
}
third[k] = diff;
k--;
i--;
j--;
}
for(int ele : third){
System.out.print(ele);
}
}
}
```

### Problem -13 Rotate an Array Element K times

You can practice this Problem on LeetCode Rotate an Array

In this we can have k can be positive or zero or Negative , and based on this we can have different cases to solve. In the following images i draw different cases.

If k is zero it do nothing. If k is greater than the length of the array, e.g k is 25. so we do 25%LengthOfTheArray. e.g 25 % arr.length and we get the value of k. If k is negative e.g k = -3 so we do the arr.length + k . (5 -3) so k=2.

There would be a case where k is negative and greater than the length e.g k is -25. so we do arr.length + (k % arr.length) . For e.g Â 5 + (-25%5) so 5 + 0 = 5 so k is 5.

Â Full Source Code ðŸ‘‡

```
class RotateAnArray13{
static void reverse(int arr[], int i, int j){
while(i<j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] =temp;
i++;
j--;
}
}
public static void main(String[] args) {
int k = 3;
int arr[] = {10,20,30,40,50};
k = k % arr.length; // range case handle
// Negative case handle
if(k<0){
k = arr.length + k;
}
// reverse the first part of the array
reverse(arr, 0, arr.length-k-1);
// reverse the second part of the array
reverse(arr, arr.length-k, arr.length-1);
reverse(arr, 0, arr.length-1);
for(int ele : arr){
System.out.println(ele);
}
}
}
```

### Problem-14 Convert array into Zig-Zag fashion

Given an array ofÂ DISTINCTÂ elements, rearrange the elements of array in zig-zag fashion in O(n) time. The converted array should be in formÂ a < b > c < d > e < f. Input: arr[] = {4, 3, 7, 8, 6, 2, 1} Output: arr[] = {3, 7, 4, 8, 2, 6, 1} Input: arr[] = {1, 4, 3, 2} Output: arr[] = {1, 4, 2, 3}

*Approach is => Â loop start to end , then check if the first element is greater than second element so swap it Â , else if first element is < second element so swap second time. So for this maintain a flag , and compliment every time.*

```
int arr[] = {4, 3, 2, 8, 6, 7, 1};
int temp = 0;
boolean flag = true;
for(int i = 0;i<arr.length-1;i++) {
if(flag) {
if( arr[i]>arr[i+1]) {
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
else {
if( arr[i]<arr[i+1]) {
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
flag = !flag;
}
System.out.println("ZigZag Array is ");
for(int a : arr) {
System.out.println(a);
}
}
```

### Problem-15 Sort the Array 0 and 1

Given an integer array A that contains only integers 0 and 1. Write a function to sort this array. Find a solution which scans the array only once. Don't use extra array. You need to change in the given array itself. So no need to return or print anything.

Input format :

Sample Input :

7

0 1 1 0 1 0 1

Sample Output :

0 0 0 1 1 1 1

*Approach* is First count all the zeroâ€™s. Then start from 0th index and go till count and fill all the zeroâ€™s there And rest after count to array length -1 fill the 1â€™s.

```
int arr[] = { 0, 1, 0, 1, 1, 1,0,1,1,0,0 };
int count = 0;
for(int i : arr) {
if(i==0) {
count++;
}
}
for(int i = 0; i<count; i++) {
arr[i] = 0;
}
for(int i = count; i<arr.length; i++) {
arr[i] = 1;
}
System.out.println("Arrange Array is ");
for(int i : arr) {
System.out.print(i+ " ");
```

### Problem-16 Dutch National Flag Problem

According to the Wiki TheÂ Dutch national flag problemÂ (DNF)Â is a programming problem proposed byÂ Edsger.Â TheÂ flag of the NeitherLands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

Given an integer array containing only 0s, 1s and 2s. Write a solution to sort this array using one scan only. You need to change in the given array itself. So no need to return or print anything.

Input format : Line 1 : Integer n (Array Size) Line 2 : Array elements (separated by space) Sample Input: 7 0 1 2 0 2 0 1 Sample Output: 0 0 0 1 1 2 2

You can practice this problem Here Leet Code Sort Color Problem

Approach is Maintain low mid high pointers Low and mid on 0 And high is ar.length-1 If element found is 0 then swap(low, mid) so mid++ low ++ , If element found is 1 so mid++ If element found is 2 then swap(low, mid)so high â€” In all the above cases swap

```
public class DutchNationalFlagProblem {
static int arr [] = {0 ,1,2 ,0, 2, 0, 1};
static void swap(int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
public static void main(String[] args) {
int low = 0 , mid = 0;
int high = arr.length-1;
while(mid<=high) {
switch(arr[mid]) {
case 0:
swap(low,mid);
low++;
mid++;
break;
case 1:
mid++;
break;
case 2:
swap(mid, high);
high--;
break;
}
}
for(int i : arr) {
System.out.print(i+ " ");
}
}
}Â
```

### Problem-17 Running Sum of 1D Array

Input: nums = [1,2,3,4]
Output: [1,3,6,10]

The Output is based on [1, 1+2, 1+2+3, 1+2+3+4]

Running Sum Problem - LeetCode

```
class RunningSum {
public static void main(String args[]) {
int arr[] = {1,2,3,4};
int[] result = new int[nums.length];
result[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
result[i] = result[i - 1] + nums[i];
}
for(int ele: result){
System.out.println(ele);
}
}
}
```

### Problem -18 Pair Diff Problem

Following is the Image to explain the problem statement

Approach - 1 Brute Force Approach

```
static void bruteForce() {
int arr[] = {11,2,7,9, 15};
int diff = 2;
for(int i = 0; i<arr.length-1; i++) {
for(int j = 0; j<arr.length-1; j++) {
// we need to do from 0 to check the diff becuase u dont know it is on the left or right
if(i!=j && arr[i]- arr[j]== diff) {
System.out.println(arr[i]+" "+arr[j]);
return ;
}
}
}
}
```

Approach -2 Two Pointer Approach

```
static void twoPointor() {
int arr[] = {11,2,7,9, 15};
int diff = 2;
// Step-1 Sort It
Arrays.sort(arr); // 2, 7, 9 , 11, 15
int i = 0; // first pointor on ith
int j = 1;// second pointor on jth
while(j<arr.length) {
int current = arr[j] - arr[i];
if(current<diff) { // current value is less than the diff it means jth value is smaller so move next to j , as it is on sorted array
j++;
}
else
if(current>diff) { // if current value is > diff so it means need to move i
i++;
if(i==j) { // and during move i if i and j are on same location so move j
j++;
}
}
else
if(current == diff) {
System.out.println(arr[i]+" "+arr[j]);
return;
}
}
}
```

### Problem -19 Find the Missing Number in given N Natural Numbers

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Write an efficient code to find the missing integer. Input: arr[] = {1, 2, 4, 6, 3, 7, 8}â€¨Output: 5 Input: arr[] = {1, 2, 3, 5}â€¨Output: 4

*Approach**-1 Sum of Array with Low Range to Max Range Â 1 + 2 + 3 + 4 + 5 = 15*

*Sum of Original Array 1 + 2 + 3 + 5 = 11*

*15-11 = 4 (Missing Number)*

**Approach**-2 Using Bitwise XOR

```
static void approach() {
int arr[] = {2,1,3,5,6};
int x = 0;
int y = 0;
int min = 1;
int max = 6;
for(int i = 0; i<arr.length; i++ ) {
x = x ^ arr[i];
}
for(int i=min;i<=max; i++) {
y = y ^ i;
}
System.out.println("Result is "+(x^y));
}
```

### Problem-20 Appear Only once

Given a sorted arrayÂ A, sizeÂ N, of integers; every element appears twice except for one. Find that element that appears once in array. 1 1 2 2 3 3 4 50 50 65 65 Output: 4

Approach-1 Using Hashing

```
int arr[] = {65, 2, 1, 2 ,3 ,50 ,4 ,3 ,50 ,1, 65};
Arrays.sort(arr);
int hash[] = new int[100];
for(int i = 0; i<arr.length; i++) {
hash[arr[i]] = ++hash[arr[i]];
}
for(int i =0 ; i<hash.length; i++) {
if(hash[i]==1) {
System.out.println("Once Appear "+i);
break;
}
}
```

Approach-2 Using XOR

```
static void findElementAppearOnlyOnce() {
int arr[] = {1, 1 ,2 ,2, 3, 3 ,4 ,50, 50, 65, 65};
int ans = 0;
for(int i = 0; i<arr.length; i++) {
ans = ans ^ arr[i];
}
System.out.println(ans);
}
```

### Problem-21 Binary Search Algorithm

Binary Search works on sorted array

Compare search element with the middle element in the array. If search element matches with the middle element, we say element found. Else If search element is greater than the middle element, then search element can only place in the right half after the middle element. Else on the Left half before the middle element.

```
class BinarySearchAlgo {
public static void main(String[] args) {
int arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
int low = 0;
int high = arr.length - 1;
int mid = 0;
int search = 70;
while (low < high) {
mid = (low + high) / 2;
if (search == arr[mid]) {
System.out.println("Element Found...");
return; // exit from the main function
}
if (search > arr[mid]) {
low = mid + 1; // Left to right
} else if (search < arr[mid]) {
high = mid - 1; // right to left
}
}
System.out.println("Element Not Found...");
}
}
```

That's all Folks for this tutorial , catch you in next tutorial. Happy Coding ðŸ˜€