Swapping numbers

You are given a permutation 

$p_1,p_2,...,p_n$ of numbers from $1$ to $n$.

A permutation $p_1,p_2,...,p_n$, beauty, is defined as the minimum number of adjacent swaps required to sort the permutation.

If it is allowed to swap two elements of the permutation (not necessarily adjacent) at most once, then what is the minimum beauty that you can get?

Example:

Input:  n=5, a[]={1,4,2,3,5}
Output: 1

Approach

Java

import java.util.ArrayList;

public class SwappingNumbers {
    static ArrayList<Integer> arr1 = new ArrayList<>();

    public static void main(String args[]) {
        int n = 5;
        int arr[] = { 1, 4, 2, 3, 5 };
        arr1 = new ArrayList<>();
        System.out.println(countSwaps(arr, n));

    }

    static int merge(int arr[], int temp[], int left, int mid, int right) {
        int inv_count = 0;

        /* i is index for left subarray */
        int i = left;

        /* i is index for right subarray */
        int j = mid;

        /* i is index for resultant merged subarray */
        int k = left;

        while ((i <= mid - 1) && (j <= right)) {
            if (arr[i] <= arr[j])
                temp[k++] = arr[i++];
            else {
                temp[k++] = arr[j++];

                inv_count = inv_count + (mid - i);
            }
        }

        // Copy the remaining elements of left subarray to temp
        while (i <= mid - 1)
            temp[k++] = arr[i++];

        // Copy the remaining elements of right subarray to temp
        while (j <= right)
            temp[k++] = arr[j++];

        // Copy back the merged elements to original array
        for (i = left; i <= right; i++)
            arr[i] = temp[i];

        return inv_count;
    }

    static int mergeSort(int arr[], int temp[], int left, int right) {
        int mid, inv_count = 0;
        if (right > left) {
            mid = (right + left) / 2;
            inv_count = mergeSort(arr, temp, left, mid);
            inv_count += mergeSort(arr, temp, mid + 1, right);
            // merge array
            inv_count += merge(arr, temp, left, mid + 1, right);
        }

        return inv_count;
    }

    static int countSwaps(int arr[], int n) {
        int[] left = { -1, -1 };
        int[] right = { 1, -1 };
        for (int i = 0; i < n; i++) {
            int d = arr[i] - (i + 1);
            if (d > left[0] && d != 0) {
                left[0] = d;
                left[1] = i + 1;
            } else if (d < right[0] && d != 0) {
                right[0] = d;
                right[1] = i + 1;
            }
        }
        if (left[1] != -1 && right[1] != -1) {
            int temp = arr[left[1] - 1];
            arr[left[1] - 1] = arr[right[1] - 1];
            arr[right[1] - 1] = temp;
        }

        return mergeSort(arr, new int[n], 0, n - 1);
    }

}

Customer satisfaction

Alice is the biggest seller in the town who sells notebooks. She has $N$ customers to satisfy. Each customer has three parameters $L_i$, $R_i$, and $Z_i$ denoting the arrival time, departure time, and quantity of notebooks required.

Each customer has to be supplied a total of $Z_i$ notebooks between $L_i$ and $R_i$ inclusive. What is the minimum rate of $W$ notebooks per unit time by which if Alice produces so that it satisfies the demand of each customer?

Note that Alice does not need to supply $Z_i$ to customer $i$ for per unit time but the total of $Z_i$ between $L_i$ and $R_i$ and distribution does not need to be uniform.

Example:

Input: n=3, 2 2 1
2 3 3
2 3 1

Output: 2

Approach

Java

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class CustomerSatisfaction {
    public static void main(String[] args) {
        int n = 3;
        HashMap<Integer, Long> m = new HashMap<>();
        // declare all array
        int lA[] = { 2, 2, 1 };
        int rA[] = { 2, 3, 3 };
        int zA[] = { 2, 3, 1 };

        // put in hash map
        for (int i = 0; i < n; i++) {
            int l = lA[i];
            int r = rA[i];
            int z = zA[i];
            Long c = m.getOrDefault(r, 0L) + z;
            m.put(r, c);

        }

        TreeMap<Integer, Long> tm = new TreeMap<>(m);
        long res = 0L;
        long served = 0L;
        for (Map.Entry<Integer, Long> e : tm.entrySet()) {
            served += e.getValue();
            // condition check
            if (served > res * e.getKey()) {
                res = served / e.getKey();
                if (served % e.getKey() > 0)
                    res++;
            }
        }
        System.out.println(res);
    }

}

Number of ways

There is an $N\times M$ grid in which there are $N$ rows and $M$ colums. A cell $(i,j)$ is defined as the $i^{th}$ row from the top and $j^{th}$ column from left. You are located at $(1,1)$ initially and can perform the following steps any number of times:

1. You can move any number of steps downwards.
2. You can move any number of steps towards the right.

There are some obstacles in the path.

You are initially located at $(1,1)$ and wants to reach $(N,M)$ but you are interested in knowing the number of ways you can reach $(N,M)$ from $(1,1)$. Since these numbers can huge, print it modulo $({10}^9+7)$.

Two ways are considered different if they have a different number of steps or differ in some positions.

Example:

Input: n=3,m=3,grid[][]={{.,.,.},{.,*,.},{.,.,.}};
Output: 8

Approach

Java

public class NumberOfWays {

    // define mode values
    final static long mod = (long) (1e9 + 7);

    public static void main(String args[]) {

        int n = 3;
        int m = 3;
        char grid[][] = { { '.', '.', '.' }, { '.', '*', '.' }, { '.', '.', '.' } };

        long dp[][] = new long[n][m];
        long sumrow[] = new long[n];
        long sumcol[] = new long[m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '*')
                    dp[i][j] = 0;
                else if (i == 0 && j == 0)
                    dp[i][j] = 1;
                else if (i == 0)
                    dp[i][j] = sumrow[i];
                else if (j == 0)
                    dp[i][j] = sumcol[j];
                else
                    dp[i][j] = (sumcol[j] + sumrow[i]) % mod;
                if (dp[i][j] == 0) {
                    sumrow[i] = 0;
                    sumcol[j] = 0;
                } else {
                    sumrow[i] = (sumrow[i] + dp[i][j]) % mod;
                    sumcol[j] = (sumcol[j] + dp[i][j]) % mod;
                }
            }
        System.out.println(dp[n - 1][m - 1]);
    }

}