# Arrays

### Lesson 4 - Arrays

* arrays
* math.random

## Arrays

![Remove Element from an Array in Java | LaptrinhX](https://stackabuse.s3.amazonaws.com/media/remove-an-element-from-an-array-in-java-1.png)

```java
public class Main{
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80 ,90, 100};
        System.out.println("array size is: " + arr.length);

        System.out.print("values are: ");

        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ,");
    }
}
```

```
array size is: 10
values are: 10 ,20 ,30 ,40 ,50 ,60 ,70 ,80 ,90 ,100 ,
```

**these are all the same**

```java
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80 ,90, 100};
        int[] arr2 = new int[]{10, 20, 30, 40, 50, 60, 70, 80 ,90, 100};

        int[] arr3 = new int[10];

        for (int i = 1; i <= arr3.length; i++)
            arr3[i-1] = i*10;
```

* here we used `arr3[i-1]` since the first index starts from **0** but are for loops starts from 1
* `int[] arr3 = new int[10];` we must explicitly to define the size to 10 since we can't infer the the size at the beginning

**cool way to visualize**

```java
public class Main{
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80 ,90, 100};

        System.out.println("-".repeat(arr.length*5));

        for (int i = 0; i < arr.length; i++)
            System.out.print("| " + i + "  ");

        System.out.print(" | <- Indices\n");
        System.out.println("-".repeat(arr.length*5));

        for (int i = 0; i < arr.length; i++)
            System.out.print("| " + arr[i] + " ");

        System.out.print("| <- Values\n");
        System.out.println("-".repeat(arr.length*5));
    }
}
```

```
----------------------------------------------------
| 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9   | <- Indices
----------------------------------------------------
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 | <- Values
----------------------------------------------------
```

#### Warm Up I  ⭐

בהינתן מערך חשב את הסכום של האיבר עם הקודמים לו

ex.

```
original:   1 | 2 | 3 | 4  | 5  | 6
new array:  1 | 3 | 6 | 10 | 15 | 21
```

explanation:

![simple-array-ex](https://i.ibb.co/s6fy0dP/simple-array-ex.jpg)

```java
public class Main{
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6};

        for (int i = 1; i < arr.length; i++)
            arr[i]+=arr[i-1]; // same as arr[i]= arr[i] + arr[i-1]

        for (int i = 0; i < arr.length; i++)
            System.out.print(" | " + arr[i]);
    }
}
```

```
 | 1 | 3 | 6 | 10 | 15 | 21
```

#### Warm Up II  ⭐

Read **n** number of values in an array and display it in reverse order:

```java
public class Main{
    public static void main(String[] args) {
        int n;
        while ((n = MyConsole.readInt("enter number of elements: "))<0)
            System.out.println("you entered a negative number");

        int[] arr = new int[n];

        for (int i = 0; i < n; i++)
            arr[i] = MyConsole.readInt("enter num"+ i + ": ");

        System.out.print("original: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ,");

        System.out.print("\nreversed: ");
        for (int i = n-1; i >= 0; i--)
            System.out.print(arr[i] + " ,");

    }
}
```

```
enter number of elements:  4
enter num0:  2
enter num1:  4
enter num2:  6
enter num3:  8
original: 2 ,4 ,6 ,8 ,
reversed: 8 ,6 ,4 ,2 ,
```

### now copy those values in reverse

עכשיו תעתיקו את המערך הפוך למערך אחר

```java
public class Main{
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6};
        int[] new_arr = new int[arr.length];


        for (int i = arr.length-1; i >= 0; i--) {
            new_arr[arr.length - 1 - i] = arr[i];
        }

        for (int i = 0; i < new_arr.length; i++) {
            System.out.print(new_arr[i] + " | ");
        }

    }
}
```

#### Find The max, min, avg and 2nd largest

* עכשיו במקום להכניס n מספרים הוא יגריל n מספרים
* בנוסף הוא ימצא את המינ' המקסימום וגם השני הגדול ביותר
* יודפס גם האיבר ממוצע

ex.

```
how many elements:  10
min:  100
max:  999

array:
----------------------------------------------------------------------
| 430  | 900  | 136  | 560  | 999  | 604  | 658  | 413  | 481  | 374  
----------------------------------------------------------------------

max value: 999
2nd largest value: 900
min value: 136
avg value: 555
```

solution:

```java
public class Main{
    public static void main(String[] args) {
        int n = MyConsole.readInt("how many elements: ");
        int[] arr = new int[n];
        int min_rand = MyConsole.readInt("min: ");
        int max_rand = MyConsole.readInt("max: ");

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int sum=0;

        //fill in array with random numbers
        for (int i = 0; i < n; i++)
            arr[i] = (int) ((Math.random() * ((max_rand+1) - min_rand)) + min_rand);

        //find max and min numbers
        System.out.println("\narray:\n" + "-".repeat(n*7));
        for (int i = 0; i < n; i++){
            System.out.print("| " + arr[i] + "  ");
            sum+=arr[i];

            max = Math.max(max, arr[i]); //one way to find max

            if (arr[i] < min) //one way to find min
                min = arr[i];
        }
        System.out.println("\n" + "-".repeat(n*7));


        //find 2nd largest
        int second_largest = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (second_largest< arr[i] && arr[i]!=max)
                second_largest= arr[i];
        }

        System.out.println("\nmax value: " + max);
        System.out.println("2nd largest value: " + second_largest);
        System.out.println("min value: " + min);
        System.out.println("avg value: " + sum/n);


    }
}
```

```
how many elements:  10
min:  100
max:  999

array:
----------------------------------------------------------------------
| 430  | 900  | 136  | 560  | 936  | 604  | 658  | 413  | 481  | 374  
----------------------------------------------------------------------

max value: 936
2nd largest value: 900
min value: 136
avg value: 555
```

### Duplicate elements ⭐⭐⭐

![C Exercises: Count a total number of duplicate elements in an array](https://www.w3resource.com/w3r_images/c-array-image-exercise-5.png)

ספרו כמה פעמים שי ערכים שחוזרים על עצמם

```
-----------------------
| 5 | 2 | 7 | 7 | 5 | 7
-----------------------

duplicate elements: 3
```

> Watch out not to double count duplicates

```java
import java.util.Arrays;

public class Main{
    public static void main(String[] args) {
        int[] arr = {5, 2, 7, 7, 5, 7};
        int cntr = 0;
        boolean[] marked = new boolean[arr.length];
        Arrays.fill(marked, false); // fills array with value


        for (int i = 0; i < arr.length; i++)
            for (int j = i+1; j < arr.length; j++)
                if (arr[i] == arr[j] && marked[j] == false){
                    ++cntr;
                    marked[j] = true;
                }

        System.out.println("duplicate elements: " + cntr);
    }
}
```

```
duplicate elements: 3
```

> Note: we could also write `!marked[j]` instead of `marked[j] == false`

#### Simpler version

```java
import java.util.Arrays;

public class Main{
    public static void main(String[] args) {
        int[] arr = {5, 2, 7, 7, 5, 7};
        int cntr = 0;

        for (int i = 0; i < arr.length; i++)
            for (int j = i+1; j < arr.length; j++)
                if (arr[i] == arr[j]){
                    ++cntr;
                    break;
                }

        System.out.println("duplicate elements: " + cntr);
    }
}
```

```
duplicate elements: 3
```

This also works and we **wont** count **twice** (or more) since we `break` before reaching the other doubles. By breaking we prevented ourselves from counting more than we should

####

#### version 2.1&#x20;

now print the duplicate values as well

ex.

```
| 5  | 2  | 7  | 7  | 5  | 7  

num of duplicate elements: 3
duplicates: | 5  | 7  | 7
```

```java
import java.util.Arrays;

public class Main{
    public static void main(String[] args) {
        int[] arr = {5, 2, 7, 7, 5, 7};
        int cntr = 0;
        boolean[] marked = new boolean[arr.length];
        int[] duplicates = new int[arr.length];
        int duplicateIndex = 0;

        Arrays.fill(marked, false);
        Arrays.fill(duplicates, 0);

        for (int i = 0; i < arr.length; i++)
            System.out.print("| " + arr[i] + "  ");
        System.out.println("\n");

        for (int i = 0; i < arr.length; i++)
            for (int j = i+1; j < arr.length; j++)
                if (arr[i] == arr[j] && !marked[j]){
                    ++cntr;
                    marked[j] = true;
                    duplicates[duplicateIndex++] = arr[j];
                }

        System.out.println("num of duplicate elements: " + cntr);

        System.out.print("duplicates: ");
        for (int i = 0; i < duplicateIndex; i++)
            System.out.print("| " + duplicates[i] + "  ");

    }
}
```

```
| 5  | 2  | 7  | 7  | 5  | 7  

num of duplicate elements: 3
duplicates: | 5  | 7  | 7
```

### Sorting array - Bubble Sort ⭐⭐

<https://youtu.be/xli_FI7CuzA> - link to youtube explanation

![Bubble Sort in C Example](https://prepinsta.com/wp-content/uploads/2020/05/Bubble-Sort-in-C-Example.png)

```java
public class Main{
    public static void main(String[] args) {
        int n = MyConsole.readInt("how many elements: ");
        int[] arr = new int[n];
        int min_rand = MyConsole.readInt("min: ");
        int max_rand = MyConsole.readInt("max: ");

        int digit_space = (int) Math.log10(max_rand) + 1 + 2;

        //fill in array
        for (int i = 0; i < n; i++)
            arr[i] = (int) ((Math.random() * ((max_rand+1) - min_rand)) + min_rand);

        //print original array
        System.out.println("\noriginal\n" + "-".repeat(n*digit_space));
        for (int i = 0; i < n; i++)
            System.out.print("| " + arr[i] + " ");
        System.out.println("\n" + "-".repeat(n*digit_space));

        //interesting stuff starts here
        for (int i = 0; i < arr.length; i++)
            for (int j = 0; j < arr.length-i-1; j++)
                if (arr[j] > arr[j+1]) {
                    // swap arr[j+1] and arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }

        //print sorted array
        System.out.println();
        System.out.println("sorted\n" + "-".repeat(n*digit_space));
        for (int i = 0; i < n; i++)
            System.out.print("| " + arr[i] + " ");
        System.out.println("\n" + "-".repeat(n*digit_space));
    }
}
```

```
how many elements:  10
min:  100
max:  2000

original
------------------------------------------------------------------------
| 438  | 897  | 863  | 608  | 371  | 1581  | 1885  | 480  | 1538  | 751  
------------------------------------------------------------------------

sorted
------------------------------------------------------------------------
| 371  | 438  | 480  | 608  | 751  | 863  | 897  | 1538  | 1581  | 1885  
------------------------------------------------------------------------
```

> Time Complexity of Bubble sort is: **O(n^2)** so it isn't often used
>
> use: `System.out.print((i%15==0 && i!=0 ?"\n" : "") + "| " + arr[i] + " ");` for a nicer print

#### Adding a number to array

![array-insertion](https://i.ibb.co/tq1Fdgk/array-insertion.jpg)

```
how many elements:  5

original
------------------------------
| 43  | 93  | 41  | 61  | 57  
-----------------------------
enter new num:  100
where to add, from 0 to 5: 2

after adding num
-------------------------------------
| 43  | 93  | 100  | 41  | 61  | 57  
------------------------------------
```

```java
public class Main{
    public static void main(String[] args) {
        int n = MyConsole.readInt("how many elements: ");
        int[] arr = new int[n];
        int min_rand = 10;
        int max_rand = 99;

        //fill in array
        for (int i = 0; i < n; i++)
            arr[i] = (int) ((Math.random() * ((max_rand+1) - min_rand)) + min_rand);

        //print original array
        System.out.println("\noriginal\n----------------------------------------------------");
        for (int i = 0; i < n; i++)
            System.out.print("| " + arr[i] + "  ");
        System.out.println("\n----------------------------------------------------");

        //add number
        int newNum = MyConsole.readInt("enter new num: ");
        int index;
        while ((index= MyConsole.readInt("where to add, from 0 to "+ n+ ": ")) >n || index<0)
            System.out.println("the number is not a valid index");

        //interesting stuff
        int[] new_arr = new int[n+1];
        for (int i = 0; i < index; i++)
            new_arr[i] = arr[i];

        new_arr[index] = newNum;

        for (int i = index+1; i < n+1; i++)
            new_arr[i] = arr[i-1];



        //print sorted array
        System.out.println();
        System.out.println("after adding num\n----------------------------------------------------");
        for (int i = 0; i < n+1; i++)
            System.out.print("| " + new_arr[i] + "  ");
        System.out.println("\n----------------------------------------------------");
    }
}
```

### Remove Elements from array

```java
public class Main{
    public static void main(String[] args) {
        int n = MyConsole.readInt("how many elements: ");
        int[] arr = new int[n];
        int min_rand = 1;
        int max_rand = 4;

        //fill in array with random numbers
        for (int i = 0; i < n; i++)
            arr[i] = (int) ((Math.random() * ((max_rand+1) - min_rand)) + min_rand);

        //print array
        System.out.println("array:");
        System.out.println("-".repeat(n*5));
        for (int i = 0; i < n; i++)
            System.out.print("| " + arr[i] + "  ");
        System.out.println("\n" + "-".repeat(n*5));

        //here we start
        int num2remove = MyConsole.readInt("whom to remove: ");
        int countRemaining = 0;

        //count elements that we will leave
        for (int i = 0; i < n ; i++)
            if (arr[i]!=num2remove)
                countRemaining++;

        int[] arr_remaining = new int[countRemaining];
        int remainingIndex = 0;

        for (int i = 0; i < n; i++){
            if (arr[i]!=num2remove){
                arr_remaining[remainingIndex] = arr[i];
                ++remainingIndex;
            }
        }

        //print array
        System.out.println("array:");
        System.out.println("-".repeat(countRemaining*5));
        for (int i = 0; i < arr_remaining.length; i++)
            System.out.print("| " + arr_remaining[i] + "  ");
        System.out.println("\n"+ "-".repeat(countRemaining*5));
    }
}
```

```
how many elements:  10
array:
--------------------------------------------------
| 4  | 4  | 2  | 3  | 4  | 1  | 1  | 3  | 1  | 4  
--------------------------------------------------
whom to remove:  4
array:
------------------------------
| 2  | 3  | 1  | 1  | 3  | 1  
------------------------------
```

### הדפסת משולשים

version 2

```java
public class Main{
    public static void main(String[] args) {
        int n = 4;

        for (int i = 0; i < n; i++)
            System.out.println("*".repeat(i));

        for (int i = n-1; i > 0; i--)
            System.out.println("*".repeat(i));
    }
}
```

```
*
**
***
***
**
*
```

### If we have time

check if an array can be splitted such that the sum of left side of the splitting is equal to the sum of the right side