### 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 = nums;
for (int i = 1; i < nums.length; i++) {

result[i] = result[i - 1] + nums[i];
}
for(int ele: result){
System.out.println(ele);
}
}
}``````

### 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 How XOR Works Compute the XOR of N natural number and Compute the Given Array and XOR Both so you get the missing number
``````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;
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
}
}