GFG Auto Run Team RIO commented Solutions

Question 1

Java Solution with comments

class Solution{
    public boolean solve(int N, String S1, String S2, String S3){
    //convert the strings into character arrays
    char[] ch1=S1.toCharArray();
    char[] ch2=S2.toCharArray();
    char[] ch3=S3.toCharArray();

    //sort all three  arrays
    Arrays.sort(ch1);
    Arrays.sort(ch3);
    Arrays.sort(ch2);

    //check if any two arrays are equal
    //if any two arrays found equal then return true otherwise return false

    //comparing ch1 and ch2 arrays 
    int flag=0;
    for(int i=0;i<ch1.length;i++){
        if(ch1[i]!=ch2[i]) 
            {
                flag=1;
                break;
            }
    }
    // flag==1 means there exist a index where characters are not same.
    if(flag==0) return true;   


    //if ch1 and ch2 are not equal then compare ch1 and ch3 array
    flag=0;
    for(int i=0;i<ch1.length;i++){
        if(ch1[i]!=ch3[i]) 
        {
            flag=1;
            break;
        }
    }
    if(flag==0) return true; 

    // ch1 and ch3 are not equal then compare ch2 and ch3 array
    flag=0;
    for(int i=0;i<ch2.length;i++){
        if(ch2[i]!=ch3[i]) 
        {
            flag=1;
            break;
        }
    }
    if(flag==0) return true; 

    return false;//if all arrays are different return false
    }
}

Question 2

Java Solution with comments

class Solution {
    public static int solve(int N, int S) {
        /*approch: To make the product minimum  we will get as many possible occurrences
                   of 1 as possible (because 1 is smallest possible element of the array).
                we place 1 at n-1 indices and at last index we balance the sum.
                so last index value = S-(N-1).
                    */ 


        return S-(N-1);

    }
}

Question 3

Java Solution with comments

class Solution { 
    boolean checkSorted(int N, int arr[]) 
    { 

        //The sorted array will look like [1,2,3,4,...n]
        //we can observe that the position of k is at index (k-1). [k is any natural number]
        // so our task is to place the elements at their actual position
        // and  if it happens in exactly 2 swaps then return true otherwise return false.



        if(N==1) //single element can not be swapped.
            return false;
        int c=0; //counter to count the swaps
        for(int i=0;i<N;i++)
        {
            if(arr[i]!=i+1)  /*if ith element is at wrong position 
                            then swap it with element placed at its actual position*/
            {
               int temp= arr[arr[i]-1];  
               arr[arr[i]-1]=arr[i];
               arr[i]=temp;
                c++; //increase the counter by 1

                if(arr[i]!=i+1)   /*after swapping check again,if element  at ith position is at wrong position 
                            then swap it with element placed at its actual position*/
                {
                   temp= arr[arr[i]-1];
                    arr[arr[i]-1]=arr[i];
                    arr[i]=temp;
                    c++; // again increase counter by 1
                }
            }
        }
        if(c==0||c==2) //for counter = 0(already sorted array) ,we can swap same pair of index two times to make counter=2.
        return true;
        return false;
    }
}

Question 4

Java Solution with comments

class line {
    public long m, c;
    line() {
        m = 0;
        c = 0;
    }
    public long getY(long x) { return m * x + c; }
} class Solution {
    line bit[];
    void insert(int id, int l, int r, line nline) {
        if (l == r) {
            if (bit[id].getY(l) <= nline.getY(l)) bit[id] = nline;
            return;
        }
        int mid = (l + r) / 2;
        if (nline.getY(l) >= bit[id].getY(l) &&
            nline.getY(mid) >=
                bit[id].getY(mid)) // intersection point lie in [mid+1,r]
        {
            line tmp = nline;
            nline = bit[id];
            bit[id] = tmp;
            insert(2 * id + 1, mid + 1, r, nline);
        } else if (nline.getY(l) <= bit[id].getY(l) &&
                   nline.getY(mid) <= bit[id].getY(mid)) {
insert(2 * id + 1, mid + 1, r, nline);
        } else if (nline.getY(r) >= bit[id].getY(r) &&
                   nline.getY(mid + 1) >=
                       bit[id].getY(mid +
                                    1)) // intersection point lie in [l,mid]
        {
            line tmp = nline;
            nline = bit[id];
            bit[id] = tmp;
            insert(2 * id, l, mid, nline);
        } else if (nline.getY(r) <= bit[id].getY(r) &&
                   nline.getY(mid + 1) <= bit[id].getY(mid + 1)) {
            insert(2 * id, l, mid, nline);
        } else {
            return;
        }
    }

    long get(int id, int l, int r, long x) {
        long y = bit[id].getY(x);
        if (l == r) {
            return y;
        }
        int mid = (l + r) / 2;
        if (x <= mid)
            return Math.max(y, get(2 * id, l, mid, x));
        else
            return Math.max(y, get(2 * id + 1, mid + 1, r, x));
    }
    ArrayList<Long> solve(int N, int A[], int B[], int Q, int Queries[]) {
        int mxK = Math.min(10 * N, 100000);
        bit = new line[4 * mxK + 5];
        for (int i = 0; i < 4 * mxK + 5; i++) bit[i] = new line();
        for (int i = 0; i < N; i++) {
            line l = new line();
            l.m = A[i];
            l.c = B[i];
            insert(1, 1, mxK, l);
}
        ArrayList<Long> ans = new ArrayList<Long>();
        for (int K = 0; K < Q; K++) {
            ans.add(get(1, 1, mxK, Queries[K]));
        }
        return ans;
        
    }
}