Bag of Tokens

You have an initial power of P, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).

Your goal is to maximize your total score by potentially playing each token in one of two ways:

1. If your current power is at least tokens[i], you may play the ith token face up, losing tokens[i] power and gaining 1 score.

2. If your current score is at least 1, you may play the ith token face down, gaining tokens[i] power and losing 1 score.

Each token may be played at most once and in any order. You do not have to play all the tokens.

Return the largest possible score you can achieve after playing any number of tokens.

Example:

Input: tokens = [100,200], P = 150
Output: 1
Explanation: Play the 0th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1st token since you cannot play it face up to add to your score.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

int bagOfTokensScore(vector<int> &tokens, int P)
{
    //sort the array
    sort(tokens.begin(), tokens.end());
    int maxScore = 0;
    int currScore = 0;
    int start = 0, end = tokens.size() - 1;

    //apply two pointer
    while (start <= end)
    {
        if (P - tokens[start] >= 0)
        {
            P -= tokens[start];
            currScore += 1;
            maxScore = max(maxScore, currScore);
            start += 1;
        }
        else if (currScore >= 1)
        {
            P += tokens[end];
            currScore -= 1;
            end -= 1;
        }
        else
        {
            break;
        }
    }

    return maxScore;
}

int main()
{
    vector<int> tokens = {100, 200};
    int P = 150;

    cout << bagOfTokensScore(tokens, P);

    return 0;
}

Advantage Shuffle

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

struct cmp
{
    bool operator()(pair<int, int> p1, pair<int, int> p2)
    {
        return p1.first > p2.first;
    }
};
vector<int> advantageCount(vector<int> &A, vector<int> &B)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, 
                   cmp> pq;

    for (int i = 0; i < B.size(); i++)
    {
        pq.push({B[i], i});
    }
    sort(A.begin(), A.end());
    vector<int> left;
    vector<int> ans(A.size());
    for (int i = 0; i < A.size(); i++)
    {
        if (A[i] > pq.top().first)
        {
            ans[pq.top().second] = A[i];
            pq.pop();
        }
        else
        {
            left.push_back(A[i]);
        }
    }
    int i = 0;
    while (!pq.empty())
    {
        ans[pq.top().second] = left[i++];
        pq.pop();
    }
    return ans;
}

int main()
{
    vector<int> A = {2, 7, 11, 15};
    vector<int> B = {1, 10, 4, 11};

    vector<int> res = advantageCount(A, B);

    cout << "[";
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i];
        if (i != res.size() - 1)
        {
            cout << ", ";
        }
    }
    cout << "]";

    return 0;
}

Greedy Florist

A group of friends wants to buy a bouquet of flowers. The florist wants to maximize his number of new customers and the money he makes. To do this, he decides he'll multiply the price of each flower by the number of that customer's previously purchased flowers plus 1. The first flower will be the original price, the next will be, and so on.
Given the size of the group of friends, the number of flowers they want to purchase, and the original prices of the flowers, determine the minimum cost to purchase all of the flowers.

Example:

Input:  n=5, k = 3, arr[]={1,3,5,7,9}
Output: 29

Approach

Java

public class GreedyFlorist {
    public static void main(String[] args) {
        int k = 3;
        int arr[] = { 1, 3, 5, 7, 9 };
        int res = getMinimumCost(k, arr);
        System.out.println(res);
    }
    static int getMinimumCost(int k, int[] arr) {
        int n = arr.length;
        arr = selectionSorting(arr, n);
        int ans = 0;
        int l = 0;
        for (int i = 0; i < Math.min(k, n); i++) {
            ans = (ans + (1 + l) * arr[i]);
        }
        l++;
        int cnt = 0;
        for (int i = k; i < n; i++) {
            ans = (ans + (1 + l) * arr[i]);
            cnt++;
            if (cnt == k) {
                cnt = 0;
                l++;
            }
        }
        return ans;
    }
    static int[] selectionSorting(int[] arr, int N) {
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (arr[min] < arr[j]) {
                    min = j;
                }
            }
            // Swapping element
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
        return arr;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int n = 5, k = 3;
    long long int arr[n] = {1, 3, 5, 7, 9};

    sort(arr, arr + n, greater<long long int>());
    long long int ans = 0;
    long long int l = 0;
    for (long long int i = 0; i < min(k, n); i++)
    {
        ans = (ans + (1 + l) * arr[i]);
    }
    l++;
    int cnt = 0;
    for (long long int i = k; i < n; i++)
    {
        ans = (ans + (1 + l) * arr[i]);
        cnt++;
        if (cnt == k)
        {
            cnt = 0;
            l++;
        }
    }
    cout << ans << "\n";
    return 0;
}

Smallest Range II

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once).
After this process, we have some array B.
Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

Input: A = [1,3,6], K = 3
Output: 3

Approach

Java

import java.util.Arrays;

public class SmallestRangeII {
    public static void main(String[] args) {
        int[] A = { 1, 3, 6 };
        int K = 3;
        System.out.println(smallestRangeII(A, K));
    }

    static public int smallestRangeII(int[] A, int K) {
        if (A.length <= 1)
            return 0;
        Arrays.sort(A);
        int ans = A[A.length - 1] - A[0];
        int r = A[A.length - 1] - K;
        int l = A[0] + K;
        for (int i = 0; i < A.length - 1; i++) {
            int max = r, min = l;

            if (A[i] + K > r)
                max = A[i] + K;

            if (A[i + 1] - K < l)
                min = A[i + 1] - K;

            if (ans > (max - min))
                ans = max - min;
        }
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int smallestRangeII(vector<int> &A, int K)
{
    multiset<int> st;
    int n = A.size();
    sort(A.begin(), A.end());
    if (K == 0)
        return A[n - 1] - A[0];
    if (n == 1)
        return 0;
    int ans = A[n - 1] - A[0];
    int max1 = A[n - 1];
    for (int i = 0; i < n; i++)
        st.insert(A[i]);

    for (int i = 0; i < n; i++)
    {
        if (st.find(A[i]) != st.end())
            st.erase(st.find(A[i]));
        A[i] = A[i] + 2 * K;
        st.insert(A[i]);
        auto it = st.begin();
        max1 = max(max1, A[i]);
        int min1 = *it;
        ans = min(ans, max1 - min1);
    }
    return ans;
}

int main()
{
    vector<int> A = {1, 3, 6};
    int K = 3;
    cout << smallestRangeII(A, K);
    return 0;
}

Group the People Given the Group Size They Belong To

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size groupSizes[i].

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example 1:

Input: groupSizes = {3,3,3,3,3,1,3}
Output: [[5],[0,1,2],[3,4,6]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class GroupSize {
    public static void main(String[] args) {
        int[] groupSizes = { 3, 3, 3, 3, 3, 1, 3 };
        List<List<Integer>> group = groupThePeople(groupSizes);
        System.out.println(Arrays.asList(group));
    }

    // function to group the peoples
    static List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<int[]> v = new ArrayList<int[]>();
        for (int i = 0; i < groupSizes.length; i++)
            v.add(new int[] { groupSizes[i], i });

        // sort the vector pair array
        Collections.sort(v, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int i = 0;
        int n = v.size();

        // iterate till the length of array
        while (i < n) {
            List<Integer> x = new ArrayList<Integer>();
            int p = v.get(i)[0] - 1;
            while (i + 1 < n && v.get(i)[0] == v.get(i + 1)[0] && p > 0) {
                x.add(v.get(i)[1]);
                i++;
                p--;

            }
            x.add(v.get(i)[1]);
            i++;
            res.add(x);
        }
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to group the peoples
vector<vector<int>> groupThePeople(vector<int>& groupSizes) 
{
        vector<pair<int,int>> v;
        for(int i=0;i<groupSizes.size();i++)
               v.push_back({groupSizes[i],i});

      //sort the vector pair array
       sort(v.begin(),v.end());
       vector<vector<int>> res;
       int i=0;
       int n=v.size();

        //iterate till the length of array
        while(i<n)
         {
            vector<int>x;
            int p=v[i].first-1;
            while(i+1<n&&v[i].first==v[i+1].first&&p>0) 
            {
                x.push_back(v[i].second);
                i++;
                p--;
                
            }
            x.push_back(v[i].second);
            i++;
            res.push_back(x);
         }
        return res;
}
int main()
{
    vector<int > groupSizes ={3,3,3,3,3,1,3};
    vector<vector<int>> group=groupThePeople(groupSizes);
    cout<<"[";
    for(int i=0;i<group.size();i++)
      {
          cout<<"[";
          for(int j=0;j<group[i].size();j++)
            {
                cout<<group[i][j];
                if(j!=group[i].size()-1)
                   cout<<",";
            }
            cout<<"]";
            if(i!=group.size()-1)
              cout<<",";
      }
     cout<<"]";
     return 0;
}