Leetcode 368. Largest Divisible Subset solution

Problem statement could be found @https://leetcode.com/problems/largest-divisible-subset/

Approach -

For every element n, check previous (n-1) elements and see if there modulo is zero. Whenever modulo is zero, store the chain length and index for the max value



Solution

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
       
        if (nums.size() <=1){
            return nums;
        }
       
        sort(nums.begin(), nums.begin() + nums.size());
        int *indexArr = new int[nums.size()];
        int *sizeArr = new int[nums.size()];
       
        for(int i=0;i<nums.size();i++){
            indexArr[i] = i;
            sizeArr[i] = 0;
        }
        int maxSize = 0;
        int maxIndex = 0;
        for(int i=0;i<nums.size();i++){
            for (int j=i-1;j>=0;j--){
                if ((nums[i]%nums[j]) == 0){
                    if (sizeArr[i] < (sizeArr[j] +1)){
                        sizeArr[i] = sizeArr[j] + 1;
                        indexArr[i] = j;
                        if (maxSize < sizeArr[i]){
                            maxSize = sizeArr[i];
                            maxIndex = i;
                        }
                    }
                   
                }
            }
        }
        vector<int> retVal;
        while (indexArr[maxIndex] != maxIndex){
            retVal.push_back(nums[maxIndex]);
            maxIndex = indexArr[maxIndex] ;
        }
        retVal.push_back(nums[maxIndex]);
        vector<int> opRetVal;
       
       for (int i=retVal.size()-1;i>=0;i--){
            opRetVal.push_back(retVal[i]);
        }
        return opRetVal;
    }
};

Leetcode 396. Rotate Function solution

Problem statement could be found @https://leetcode.com/problems/rotate-function/

Solution Approach-
Lets consider the numbers given in example [4,3,2,6] so we have following combinations
4 * 0 + 3* 1 + 2 *2 + 6 * 3
3 * 0 + 2 * 1 + 6 * 2 + 4 * 3
2 * 0 + 6 * 1 + 4 * 2 + 3 * 3
6 * 0 +  4 * 1 + 3 * 3 + 2 * 3

If one looks it closely it would seems like a sliding window for following array
4, 3,2,6,4,3,2

Above step means append  (n-1) elements to original vector.

Another optimization is  between first and second step, the difference is

In first step
Step 1. totalSum = 25
Step2. pSum = 3 +  2 + 6
Step 3. now in step2, total value has to be decreased by pSum as we shift left and now 4 * 3 has to be added, where 4 is the new element value & 3 (vector size -1).

At every slide of window these steps are applied



Following is the code

class Solution {
public:
   
    int maxRotateFunction(vector<int>& A) {
        if (A.size() == 0)
            return 0;
           
       
         if (A.size() == 1)
            return A[0]*0;
           
       int maxSum  = 0;
       int pSum = 0;
       int size = A.size();
     
       for (int i=0;i<size;i++) {
           maxSum = maxSum + (A[i] * i);
           if (i != 0 )
            pSum = pSum + A[i];
       }
       for (int i=0;i<size-1;i++){
           A.push_back(A[i]);
       }
      int gMax = maxSum;
    //  size = A.size();
      for (int i=1;i<size ;i++){
          //maxSum - pSum;
          maxSum  = maxSum - pSum + A[size+i-1] * (size - 1);
          pSum = pSum - A[i]  + A[i+size-1];
          if (maxSum > gMax)
            gMax = maxSum;
      }
      return gMax;
    }
};