index

2020 A - Question 1 - powerful number

A powerful number is a positive integer m such that for every prime number p dividing m, p2 also divides m

The following is a list of all powerful numbers between 1 and 200:

1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, 144, 169, 196, 200

Solution

public class test2020A_Q1 {
    //check if prime number
    public static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++)
            if (n % i == 0)
                return false;

        return true;
    }

    //get array of all prime numbers that divide n
    public static int[] prime_dividers(int n) {
        ArrayList<Integer> listOfPrimes = new ArrayList();

        // prime must be greater than 1
        if (n <= 1)
            return new int[0];

        if (n <= 2)
            return new int[]{2};

        for (int i = 2; i <= n; i++)
            if (isPrime(i) && n%i==0)
                listOfPrimes.add(i);

        int[] primes = new int[listOfPrimes.size()];
        for (int i = 0; i < primes.length; i++)
            primes[i] = listOfPrimes.get(i);

        return primes;
    }

    public static boolean powerful(int n) {
        int[] primes_to_check = prime_dividers(n);

        if (n == 1)
            return true;

        if (primes_to_check.length==0)
            return false;

        for (int i = 0; i < primes_to_check.length; i++)
                if(n%primes_to_check[i]!=0 || n % Math.pow(primes_to_check[i], 2)!=0 )
                    return false;

        return true;
    }



    public static void main(String[] args) {
        for (int i = -10; i <= 100; i++) {
            if (powerful(i))
                System.out.println(i + " is powerful number");
        }
    }
}

1 is powerful number
4 is powerful number
8 is powerful number
9 is powerful number
16 is powerful number
25 is powerful number
27 is powerful number
32 is powerful number
36 is powerful number
49 is powerful number
64 is powerful number
72 is powerful number
81 is powerful number
100 is powerful number

2020 A - Question 2

Solution

public class test2020A_Q2 {
    public static int balanced(String str){
        int countS=0, countR=0, s_equals_r =0;
        System.out.print("[");


        for (int i = 0; i < str.length(); i++) {
            switch (str.charAt(i)){
                case 'S':
                    countS++;
                    if (countS==countR){
                        System.out.print(str.substring(0,i+1) + " ");
                        s_equals_r++;
                    }
                    break;
                case 'R':
                    countR++;
                    if (countS==countR){
                        System.out.print(str.substring(0,i+1) + " ");
                        s_equals_r++;
                    }
                    break;
                default: //if contains letters other than S or R
                    System.out.print("]\t");  
                    return 0;
            }
        }

        System.out.print("]\t");
        return s_equals_r;
    }

    public static void main(String[] args) {
        System.out.println(balanced("SRRS"));
        System.out.println(balanced("RSSRS"));
        System.out.println(balanced("RSS"));
        System.out.println(balanced("RSAS")); //Can fix this with StringBuilder instead of printing but its easier
    }
}

[SR SRRS ]    2
[RS RSSR ]    2
[RS ]    1
[RS ]    0

Arrays

2020 A - Question 3

Solution

public class test2020A_Q3 {

    public static void fillIn(int[][] a){
        int num = 1;

        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                a[i][j] = num++;
    }

    public static void spiral(int[][] a){
        for (int k = 0; k < a.length/2; k++) {

            for (int j = k; j < a.length - k; j++)
                System.out.print(a[k][j]+ " ");

            for (int i = k+1; i < a.length - k; i++)
                System.out.print(a[i][a.length-1-k]+ " ");

            for (int j = a.length- 2-k; j>=k; j--)
                System.out.print(a[a.length-1-k][j]+ " ");

            for (int i = a.length- 2-k; i>k; i--)
                System.out.print(a[i][k]+ " ");

        }

        if (a.length%2==1)
            System.out.print(a[a.length/2][a[0].length/2]+ " ");


    }
    public static void main(String[] args) {
        final int SIZE_ROWS = 4;
        final int SIZE_COLS = 4;

        int[][] matrix = new int[SIZE_ROWS][SIZE_COLS];
        fillIn(matrix);

        spiral(matrix);
    }
}

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

2020 A - Question 4 - Ellipse

Solution

public class Point {
    public double x;
    public double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double distance(Point p) {
        double xDis = x - p.x;
        double yDis = y - p.y;
        return Math.sqrt(xDis*xDis + yDis*yDis);
    }

    public static double distance(Point p1, Point p2) {
        double xDis = p1.x - p2.x;
        double yDis = p1.y - p2.y;
        return Math.sqrt(xDis*xDis + yDis*yDis);
    }

    public boolean equals(Point p) {
        return x ==p.x && y ==p.y;
    }
}

class Ellipse {
    Point point_p, point_q;
    double n;

    public Ellipse(double x_p, double y_p, double x_q, double y_q, double n) {
        point_p = new Point(x_p, y_p);
        point_q = new Point(x_q, y_q);
        this.n = n;
    }

    public Ellipse(Ellipse other) {
        point_p = new Point(other.point_p.x, other.point_p.y);
        point_q = new Point(other.point_q.x, other.point_q.y);
        this.n = other.n;
    }

    //0 on circumference
    //1 outside ellipse
    //-1 inside ellipse
    public int where(Point p) {
        double res = Point.distance(point_p, p) + Point.distance(point_q, p);

        if (res == n)
            return 0;
        else if (res < n)
            return -1;
        else
            return 1;
    }

//    @Override
    public boolean equals(Ellipse other) {
//        return n==other.n && point_p==other.point_p && point_q.equals(other.point_q);
        return n==other.n && point_p.equals(other.point_p) && point_q.equals(other.point_q);
    }
}

public class test2020A_Q4 {
    public static void main(String[] args) {
        Ellipse e1 = new Ellipse(-1.5, 0, 1.5,0,2.5*2);

        System.out.println(e1.where(new Point(0,2)));
        System.out.println(e1.where(new Point(0,1.99)));
        System.out.println(e1.where(new Point(0,2.01)));

        Ellipse e2 = new Ellipse(-1.5, 5, 1.5,5,2.5*2);
        System.out.println(e1.equals(e2));
        System.out.println(new Ellipse(-1.5, 0, 1.5,0,2.5*2).equals(e1));

    }
}

2020 B - Question 2 - Strings : Find Max number

public class test2020B_Q2 {
        public static int findMaxNum(String str) {
            int len = str.length();
            int max = Integer.MIN_VALUE;
            String temp = "";

            for (int i = 0; i < len; i++) {
                //Character.isDigit() - Determines if the specified character is a digit.
                if (Character.isDigit(str.charAt(i))) {
                    //if next char is also a digit, append
                    if (i < len-1 && Character.isDigit(str.charAt(i+1))) {
                        temp += str.charAt(i);
                    } else {  //if next char isn't a digit (but this char is) or end of the string
                        temp += str.charAt(i);

                        int num = Integer.parseInt(temp);
                        if (max < num)
                            max = num;
                        temp = "";
                    }
                }
            }
            if (max!=Integer.MIN_VALUE)
                return max;
            return -1;
        }



    public static void main (String[] args) {
        String str1 =  "93&*ab1234crt70";
        System.out.println("The given string is: "+str1);
        System.out.println("The max num is: "+ findMaxNum(str1) + "\n");


        str1 =  "8ab(55c#r9t";
        System.out.println("The given string is: "+str1);
        System.out.println("The max num is: "+ findMaxNum(str1) + "\n");

        str1 =  "hello";
        System.out.println("The given string is: "+str1);
        System.out.println("The max num is: "+ findMaxNum(str1));
    }
}

The given string is: 93&*ab1234crt70
The max num is: 1234

The given string is: 8ab(55c#r9t
The max num is: 55

The given string is: hello
The max num is: -1

2020 B - Question 3 - arrays : diagonal

public class test2020B_Q3 {
        public static boolean diagonal(int[][] arr) {
            int MAX_ROWS = arr.length;
            int MAX_COLS = arr[0].length;
            for (int i = 0; i < MAX_ROWS; i++)
                for (int j = 0; j < MAX_COLS; j++)
                    if (i+1 < MAX_ROWS && j+1 < MAX_COLS)
                        if (arr[i][j]!=arr[i+1][j+1])
                            return false;

            return true;

        }

    public static void main (String[] args) {
        int[][] arr = { {1, 2, 3, 4},
                        {5, 1, 2, 3},
                        {9, 5, 1, 2}};

        System.out.println(diagonal(arr));

        arr = new int[][]{{1, 2},
                          {2, 2}};

        System.out.println(diagonal(arr));
    }
}

true
false

2020 B - Question 5 - linked lists : Add to an ordered Linked List

img

We did this question

Test Example 3: Question 2

Test Exercise: Add to an ordered Linked List

class LinkedList {
    Node head;

    LinkedList() { head = null; }

    //add before

    public LinkedList add_inorder(int elem) {
        if (head==null)
            head = new Node(elem);
        else{
            Node t = head; //transverse

            //if at beginning of list
            if (elem < head.data){
                Node node = new Node(elem);
                node.next = head;
                head = node;
                return this;
            }


            //other cases
            while (t.next != null && t.next.data < elem)
                t = t.next;
            Node node = new Node(elem);
            Node next_node = t.next;

            t.next = node;
            node.next = next_node;

        }
        return this;
    }
}

class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        System.out.println(ll);
        ll.add(1).add(2).add(4);

        ll.add_inorder(3);
        System.out.println(ll);


        ll.add_inorder(5);
        System.out.println(ll);

        ll.add_inorder(0);
        System.out.println(ll);
    }
}

LinkedList{1 ,2 ,3 ,4}
LinkedList{1 ,2 ,3 ,4 ,5}
LinkedList{0 ,1 ,2 ,3 ,4 ,5}

Test Example 2: Question 1

longest string

static String longestWord("ab cdef abc d") -> ”cdef”

Solution

public class test_example_Q1 {
    static String longestWord(String str) {
        String[] strings = str.split(" ");
        int max_length = -1;
        String max_str = "";

        for (int i = 0; i < strings.length; i++)
            if (strings[i].length() > max_length){
                max_length = strings[i].length();
                max_str = strings[i];
            }
         return max_str;
    }

    public static void main (String[] args) {
        String str1 = "ab cdef abc d";
        System.out.println(longestWord(str1));
    }
}

cdef

Test Example 2: Question 3

we did this already

Test Example 2: Question 5

simplest approach, first sort then check

public class test_example2_Q5 {
    static void bubble_sort(int[] arr) {
        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;
                }
    }

    static boolean equal(int[] a1, int[] a2){
        if (a1.length!=a2.length)
            return false;

        bubble_sort(a1);
        bubble_sort(a2);

        for (int i = 0; i < a1.length; i++)
            if (a1[i]!=a2[i])
                return false;
        return true;
    }



    public static void main (String[] args) {
        System.out.println(equal(new int[]{3,2,3,1}, new int[]{1,2,3,3}));
        System.out.println(equal(new int[]{1,2,3}, new int[]{1,2,3,3}));
    }
}

true
false