Two Sum Java Solution

Two Sum Java Solution

  May 02, 2022    

---

Problem:

Given an array of integers numbers and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.
 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Approach: 

Maintain Map with Index and handle case for duplicity so that we are not taking same element again

 

Solution:

 public int[] twoSum(int[] nums, int target) {
        int a[] = new int[2];
        HashMap<Integer, Integer> set = new HashMap<>();
        for(int i =0;i<nums.length; ++i) {
            set.put(nums[i], i);
        }
        for(int i =0;i<nums.length; ++i) {
            if(set.containsKey(target-nums[i]) && i != set.get(target-nums[i]))
            {
             a[0] = i;
            a[1] = set.get(target-nums[i]);
                return a;
            }
        }
        return a;
    }

Read More

Minimum swaps to make K together

Minimum swaps to make K together

  March 01, 2021    

---

Problem : 

Given an array of n positive integers and a number k. Find the minimum number of swaps required to bring all the numbers less than or equal to k together.

Number of Swap = number of elements <=k not connected to maxArea of connected elements <=k

So idea is count numbers less than equal to k and check for max consecutive box, subtract it from count.

Code : 

 public static int minSwap (int a[], int n, int k) {
        int consecutiveElements = 0;
        int maxSoFar = 0;
        int count = 0;
        for(int i =0 ;i<n; ++i) {
            if(a[i]<=k) {
                ++count;
                ++maxSoFar;
            }
            else
            maxSoFar = 0;
            consecutiveElements= Math.max(consecutiveElements, maxSoFar);
        }
        return count-consecutiveElements;
    }

Read More

Group Anagrams Together java solution

Group Anagrams Together java solution

  April 23, 2020    

---

Problem :

Given an array of words, print the count of all anagrams together in sorted order (increasing order of counts).
For example, if the given array is {“cat”, “dog”, “tac”, “odg”, “act”}, then grouped anagrams are “(dog, odg) (cat, tac, act)”. So the output will be 2 3.

Solution : 

So Problem is to figure out number of occurrence of characters and if there is a repeat then treat it as its anagram.

Ex  ; dog and gdo has same character occurrence so they are anagram.

Here we are going to find unique character occurrence by finding hash of the string's chars and assign this unique hash to map and increment count.

Return the sorted count.

Code : 

 public static String getHash(String cur) { // get Hash for characters of string
         char hash[]=new char[256];
         for(int i=0;i<cur.length();++i){
             char c = cur.charAt(i);
             hash[(int)(c)] = '1';
         }
         return new String(hash);
     }
     public static void fn(String a[],int n)
     {
         Map<String,Integer> hash = new HashMap<>();
         for(String cur: a) {
             String hashKey = getHash(cur);
                 hash.put(hashKey,hash.getOrDefault(hashKey,0)+1);
         }
         List<Integer> list = new ArrayList<>();
         for(Map.Entry<String,Integer> entry : hash.entrySet()) {
             list.add(entry.getValue());
         }
         Collections.sort(list);
         for(int cur:list) {
             System.out.print(cur+" ");
         }
     }

Read More

Maximum no of 1's row

Maximum no of 1's row

  April 21, 2020    

---

Problem :

Find out the row which has maximum number of 1 given that all the rows are sorted.

Example :

0 1 1 1
0 0 1 1
1 1 1 1  // this row has maximum 1s
0 0 0 0

Output: 2

Solution :

As we know that it is sorted then we know that there will be 1 at the end of the row which has max 1.

So we will start from the last column and check if it is one then we go ahead and check for CurrentColum-1.

Until we receive 0 or we are at the 0th index.

And in case if it is 0 we just change the row and assign max row id = currentRow.





Code:



 

  public static int fn(int a[][],int n,int m)
  {
   int row = 0;
   int col = m-1;
   int maxRowId = -1;
   while(row<n && col>=0) {
       if(a[row][col] == 1)
       {
           --col;
           maxRowId = row;
       }
       else
       ++row;
   }

Read More

The Tiny Miny Smallest Number

The Tiny Miny Smallest Number

  June 03, 2019    

---

Problem: You are given A and B . You have to calculate A^1 , A^2 , A^3... A^B , append result.
Find a permutation of outcome which leads to minimum Result

Example 
9 4
9^1 = 9
9^2 = 81
9^3 = 729
9^4  = 6561
9 81 729 6561
We get  9817296561


Smallest Permutation : 1125667899


We know that a number will lie from 1 to 9 , hence we can use hash to count occurrence of a number and in return print it.
Idea is to find all power and store them into hash


Code:

  public static void addIntoHash(int hash[],double num)
     {
      while(num>0)
      {
          int rem=(int)num%10;
          ++hash[rem];
          num/=10;
      }
     }
  public static StringBuilder fn(int a,int n)
  {
      int hash[]=new int[10];
      StringBuilder res=new StringBuilder();
      while(n-- >0)
      {
          double num=Math.pow(a,n+1);
          addIntoHash(hash,num);
      }
      for(int i=1;i<=9;++i)
      {
          while(hash[i]>0)
          {res.append(i);
              --hash[i];
          }
      }
      return res;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
    int a=ab.nextInt();
    int n=ab.nextInt();
    System.out.println(fn(a,n));
}

Read More

Smallest Positive missing number Constant Space

Smallest Positive missing number Constant Space

  January 16, 2019    

---

You are given an array a[] of N integers including 0. The task is to find the smallest positive number missing from the array.

Here we can use negation technique where if one element is encountered then we just negate its index value and again iterate through the array and find which index is positive and that index+1 number is answer as index starts from 0.

Before this we need to filter negative elements as we need to find missing number > 0 , so partition number such that all numbers greater than 0 are at left side.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
     public static int partition(int a[],int n)
     {
         int r=n-1;
         for(int i=n-1;i>=0;--i)
         {
             if(a[i]<=0)
             {
                 int temp=a[r];
                 a[r]=a[i];
                 a[i]=temp;
                 --r;
             }
         }
         return r;
     }
  public static int fn(int a[],int n)
  {
      int p=partition(a,n);
      //System.out.println(p+" ");
       /*for(int i=0;i<=p;++i)
      {
           System.out.print(a[i]+" ");
      }*/
      for(int i=0;i<=p;++i)
      {
          if(Math.abs(a[i])-1<=p  && a[Math.abs(a[i])-1]>0)
          a[Math.abs(a[i])-1]=-a[Math.abs(a[i])-1];
      }
      /*for(int x:a)
      System.out.print(x+" ");*/
       for(int i=0;i<=p;++i)
      {
          if(a[i]>0)
          return i+1;
      }
      return p+2;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(fn(arr,n));
}
}

}

Read More

Rotate Matrix represented in 1D inplace

Rotate Matrix represented in 1D inplace

  September 26, 2018    

---

Problem:
1-D array contained N*N elements. Assuming that the N*N elements form a matrix, you have to rotate the matrix in-place

Prerequisites :
Rotate matrix represented in N*N

Idea is to find transpose of the matrix
Then reverse every n blocks to rotate right 
OR for left rotate
Reverse whole matrix and rightRotate It.
Formula to find a[i][j]
a[col*i+j]


Code:
import java.util.*;
import java.lang.*;
import java.io.*;
class rotatematrix1d
 {
   public static void reverse(int a[],int start,int end)
   {
     while(start<end)
     {
       int temp=a[start];
       a[start]=a[end];
       a[end]=temp;
       ++start;
       --end;
     }
   }
   public static void transpose(int a[],int n)
   {
     for(int i=0;i<n;++i)
     {
       for(int j=i;j<n;++j)
       {
         int temp=a[n*i+j];
         a[n*i+j]=a[n*j+i];
         a[n*j+i]=temp;
       }
     }

     for(int x:a)
     System.out.print(x+" ");

     System.out.println();
   }
   public static void rightRotate(int a[],int n)
   {
     int i=n;
     while(i<=n*n)
     {reverse(a,i-n,i-1);
     i+=n;}
   }
   public static void leftRotate(int a[],int n)
   {
     reverse(a,0,n*n-1);

     rightRotate(a,n);
   }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
    int n=ab.nextInt();
    int arr[]=new int[n*n];
    for(int i=0;i<n*n;++i)
    arr[i]=ab.nextInt();
      transpose(arr,n);
      //rightRotate(arr,n);
      leftRotate(arr,n);
      for(int x:arr)
      System.out.print(x+" ");
    System.out.println();

}
}

Read More

Max sum path in two Array

Max sum path in two Array

  June 28, 2018    

---

Problem:

Given two sorted arrays such the arrays may have some common elements.
Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can start from any array and switch from one array to another array only at common elements.

Input:

1
5 5
1 2 3 4 5
5 6 7 8 9 

Output
45

Explanation:

1+2+3+4+5+6+7+8+9=45

Intuition:

If we look closer to the problem , it is like merge sort merge Function.
We have to maintain 2 variables for sum of both array.
When we are having common element we can choose any sum and again follow process.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class maxSumpathTwoArray
 {
  public static int fn(int a[],int b[],int n,int m)
  {
    int sum1=0,sum2=0;
    int res=0,i=0,j=0;
    while(i<n && j<m)
    {
      if(a[i]==b[j])
      {
        res+=Math.max(sum1,sum2)+a[i];
        sum1=sum2=0;
        ++i;
        ++j;
      }
      else if(a[i]<b[j])
      sum1+=a[i++];
      else
      sum2+=b[j++];
    }
    while(i<n)
    sum1+=a[i++];

    while(j<m)
    sum2+=b[j++];
    return res+Math.max(sum1,sum2);
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int m=ab.nextInt();
    int arr[]=new int[n];
    int arr2[]=new int[m];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    for(int i=0;i<m;++i)
    arr2[i]=ab.nextInt();
    System.out.println(fn(arr,arr2,n,m));
}
}
}

Read More

Equileader solution

Equileader solution

  June 27, 2018    

---

Algorithm:

First find majority element.
Now we have a index i such that i lies between 0 to n 

Left count will hold count of majority element till i and from i+1 to n we can get by totalcount-leftcount.
Now just check if both the counts are greater than window size /2

Code:


class dmg{ public int solution(int[] a) { int n=a.length; int count=1; int ele=a[0]; for(int i=1;i<n;++i) { if(a[i]==ele) ++count; else --count; if(count==0) { count=1; ele=a[i]; } } count=0; for(int i=0;i<n;++i) { if(a[i]==ele) ++count; } if(count<n/2) return 0; int lcount=0,res=0; for(int i=0;i<n;++i) { if(a[i]==ele) ++lcount; if(lcount>(i+1)/2 && (count-lcount)>(n-i-1)/2) ++res; } return res; } }

Read More

Heap Sort

Heap Sort

  June 22, 2018    

---

This sorting needs max Heap to sort Array
Algorithm:
As we know heap are balanced tree so they can be constructed using array.

We are already having array , heapify it using root i.e. n/2-1 roots are there so heapify  n/2-1times
After heapify 
Root node will have node greater than its child nodes
We will swap last node with its first node
decrement last node ,change  root to next element and heapify again


Code:

 void buildHeap(int a[], int n)
    {
        for(int i=n/2-1;i>=0;--i)
        heapify(a,n,i);
        for(int i=n-1;i>=0;--i)
        {
            int temp=a[0];
            a[0]=a[i];
            a[i]=temp;
            heapify(a,n,0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int a[], int n, int i)
    {
        int l=2*i+1;
        int r=2*i+2;
        int max=i;
        if(l<n && a[l]>a[max])
        max=l;
        if(r<n && a[r]>a[max])
        max=r;
        if(max!=i)
        {
            int temp=a[i];
            a[i]=a[max];
            a[max]=temp;
            heapify(a,n,max);
        }
    }

Read More

Search Element in Sorted and rotated Array

Search Element in Sorted and rotated Array

  June 21, 2018    

---

One of the approach will be to find rotation point and check if number is in left or right subarray , Apply Binary Search for that part.
This will take two scan of Array

In one scan we can also perform same:

Algo:
check if mid is element to be searched , if so return mid;
else one of the subarray either from left to mid OR mid to right will be sorted 
Check for sorted Array and range of number i.e. whether number lies in which range and change accordingly


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class searchSortedRotated
 {
   public static int bSearch(int a[],int x,int n)
   {
      int l=0,r=n-1;
      while(l<=r)
      {
        int mid=(l+r)>>1;
        if(a[mid]==x)
        return mid;
      //atlest one of the subarray will be sorted so check if number ranges in sorted or not
      if(a[l]<=a[mid])
      {
        if(x>=a[l] && x<a[mid])
        r=mid-1;
        else
        l=mid+1;
      }
      else //if(a[mid]>=a[r])
      {
        if(x>a[mid] && x<=a[r])
        l=mid+1;
        else
        r=mid-1;
      }
      }
      return -1;
   }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    int k=ab.nextInt();
    System.out.println(bSearch(arr,k,n));
}
}
}

Read More

Check if TicTacToe is valid

Check if TicTacToe is valid

  June 17, 2018    

---

Problem :
A Tic-Tac-Toe board is given after some moves are played. Find out if the given board is valid, i.e., is it possible to reach this board position after some moves or not.
X will be move first

https://practice.geeksforgeeks.org/problems/tic-tac-toe/0

here we are having few cases :

IF x count==o it means o should win and if x wins then it will be invalid.
IF x count==o+1 it means x will win , in that case if o wins then it will be invalid 
IF xcount-o count !=1 || 0 it means invalid
Else valid 

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class validTicToe
 {
   public static boolean wins(char a[],char t)
   {
     int win[][] = {{0, 1, 2}, // Check first row.
                 {3, 4, 5}, // Check second Row
                 {6, 7, 8}, // Check third Row
                 {0, 3, 6}, // Check first column
                 {1, 4, 7}, // Check second Column
                 {2, 5, 8}, // Check third Column
                 {0, 4, 8}, // Check first Diagonal
                 {2, 4, 6}}; // Check second Diagonal
                 for(int i=0;i<8;++i)
                 {
                   if(a[win[i][0]]==t && a[win[i][1]]==t && a[win[i][2]]==t)
                   return true;
                 }
                 return false;
   }
  public static boolean isValid(char a[])
  {
    int o=0,x=0;
    for(int i=0;i<9;++i)
    {
      if(a[i]=='X')
      ++x;
      else
      ++o;
    }
    if(x==o)
    {
      //System.out.println("eq");
      if(wins(a,'X'))
      return false;
    }
    else if(x==o+1)
    {
    //  System.out.println("x>");
      if(wins(a,'O'))
      return false;
      return true;
    }
    return false;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    char arr[]=new char[9];
    for(int i=0;i<9;++i)
    arr[i]=ab.next().charAt(0);
    System.out.println(isValid(arr));
}
}
}

Read More

Length of longest AP sequence

Length of longest AP sequence

  June 17, 2018    

---

We are given an sorted array , now we need to find longest subseqence forming A.P.
Idea is to look for every gap but it will take more time to perform that.

So we are going to fix middle element and find two element such that these 3 elements  form A.P.
This find can be done using sliding window concept
and if any sequence found then we can say that from start to fix subseqence AP=fix to k subsequence AP+1.

Base case:
if elements are >=2 then ap will be atleast of 2 size.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class longestAP
 {
  public static int fn(int a[],int n)
  {
    if(n<=2) return n;
    int dp[][]=new int[n][n];
    int res=2;
    for (int i = 0; i < n; i++)
           dp[i][n - 1] = 2;
   //fixing jth pointer and looking both side for AP pair having a[i]+a[k]==2*a[j]
    for(int j=n-2;j>=1;--j)
    {
      int i=j-1,k=j+1;
      while(i>=0 && k<n)
      {
        if(a[i]+a[k]==2*a[j])
        {
          dp[i][j]=dp[j][k]+1;
          res=Math.max(res,dp[i][j]);
          --i;
          ++k;
        }
        else
        {
         dp[i][j]=Math.max(dp[i][j],2);
          if(a[i]+a[k]<2*a[j])
          ++k;
          else
          --i;
        }
      }
      while (i >= 0)
           {
               dp[i][j] = 2;
               i--;
           }
    }
    return res;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(fn(arr,n));
}
}
}

Time : O(n^2)

Read More

Three Way Partitioning QuickSort

Three Way Partitioning QuickSort

  June 17, 2018    

---

In general , we pick an element as pivot and peform partitioning .
Now as per 3 way partitioning we will choose a range to perform partition.

Problem:
https://practice.geeksforgeeks.org/problems/three-way-partitioning/1

Here we are not bothered about the sequence we only care about left element should be less than range and right elements greater than .

So we choose two pointers 
1:start to replace less element
2: end to replace greater element

But we are not incrementing i every time as we  don't know that after swap element is at right position or not as if we swap larger element with last positioned end ,it might happen that that element can be less or greater then again recheck need to be done..

Code:


public ArrayList<Integer> threeWayPartition(ArrayList<Integer> a, int x, int y)
{
        int l=0,r=a.size()-1;
        int i=0;
        while(i<=r)
        {
            if(a.get(i)<x)
            {
                int temp=a.get(l);
                a.set(l,a.get(i));
                a.set(i,temp);
                ++l;
                ++i;
            }
            else if(a.get(i)>y)
            {
                 int temp=a.get(r);
                a.set(r,a.get(i));
                a.set(i,temp);
                --r;
            }
            else
            ++i;
          //  System.out.println(a);    
        }
       // System.out.println(a);
        return a;
        }

Read More

Largest subarray of 0's and 1's

Largest subarray of 0's and 1's

  June 16, 2018    

---

Problem
Given an array of 0's and 1's , give  size of  the  largest sub array with equal number of 0's and 1's .

Idea to change array to -1 and 1 and now problem changes to maximum subarray having sum 0.
Use a map to store least index for every sum and when we encounter same sum again it means that from that index (stored in map) to i (current) we have a subarray with sum 0.

Code

void manipulate(int a[])
    {
        for(int i=0;i<a.length;++i)
        {
            if(a[i]==0)
            a[i]=-1;
        }
    }
    int maxLen(int[] a)
    {
        manipulate(a);
         Map<Integer,Integer> m=new HashMap<>();
         int maxLen=0;
         int cursum=0;
         for(int i=0;i<a.length;++i)
         {
             cursum+=a[i];
             if(m.containsKey(cursum))
             {
                 maxLen=Math.max(maxLen,i-m.get(cursum));
             }
             else if(cursum==0)
             maxLen=i+1;
             else
             m.put(cursum,i);
         }
        // System.out.print(m+" "+cursum);
         return maxLen;
    }

Read More

Bird and maximum fruit gathering

Bird and maximum fruit gathering

  June 16, 2018    

---

Problem:

There are N trees in a circle. Each tree has a fruit value associated with it.  

A bird has to sit on a tree for 0.5 sec to gather all the fruits present on the tree and then the bird can move to a neighboring tree. It takes the bird 0.5 seconds to move from one tree to another. Once all the fruits are picked from a particular tree, she can’t pick any more fruits from that tree. The maximum number of fruits she can gather is infinite.

We are given N and M (the total number of seconds the bird has), and the fruit values of the trees. We have to maximize the total fruit value that the bird can gather. The bird can start from any tree.


Idea is to find a window with size K as 0.5 to collect 0.5 sec to move so total 1 sec to collect and move to next element.
Now calculate first window and check whether we have reached to end of array , if so return total sum.
Else traverse till we have considered every i as starting position as it is circular array then we can move from n to 0 ,1 ... 
so we keep track on that using start variable.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
  public static long fn(int a[],int n,int k)
  {
      int i=0;
      long cursum=0,res=0;
      for(;i<k && i<n;++i)
      {
          cursum+=a[i];
      }
      res=cursum;
      if(i==n)
      return res;
      int start=0;
      for(;start<n;i=(i+1)%n)
      {
          cursum+=a[i];
          cursum-=a[start++];
          if(cursum>res)
          res=cursum;
      }
      return res;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int k=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(fn(arr,n,k));
}
}
}

Read More

Merge two sorted array into a

Merge two sorted array into a

  May 26, 2018    

---

Simple approach was merge of merge sort but that take extra space

Here we doing in O(1) extra space.

Algo:
Start and check the correct position of jth element of b
add into that position , change size of array a

And import point is also check if previous element added was of b and now we are pointing to next greater element of that and it may arise that previous element is greater than this so add at previous index and don't increment i

Code:

public void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
    int i=0,j=0;
    int k=0;
    int n=a.size(),m=b.size();
    while(k<n && j<m)
    {
        if(a.get(k)<b.get(j))
               ++k;
           
         else
         {
             if(k-1>=0 && a.get(k-1)>b.get(j))
             a.add(k-1,b.get(j));
             else
              { a.add(k,b.get(j));
                n=a.size();
             ++k;
            }
             ++j;
         }
    }
    while(j<m)
    {
        a.add(b.get(j++));
    }
}

Read More

Count no. of subset having sum k

Count no. of subset having sum k

  May 26, 2018    

---

it is same like subset sum problem
We have modified that approach by having int value

Code memoized:

public static int fn(int a[],int i,int n,int sum,int memo[][])
  {
      if(sum<0)
      return 0;
      if(memo[i][sum]!=0)
      return memo[i][sum];
      if(sum==0) 
        {
            return memo[i][sum]=1;}
      if(i==n ) return 0;
      int s=1;
            return memo[i][sum]=fn(a,i+1,n,sum,memo)+fn(a,i+1,n,sum-a[i],memo);
      
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    int k=ab.nextInt();
    int memo[][]=new int[n+1][k+1];
    System.out.println(fn(arr,0,n,k,memo));
}

}

Code DP:

  public static int fn(int a[],int n,int sum)
  {
     int dp[][]=new int[n+1][sum+1]; // denotes no. of subset till n having sum=sum
     for(int i=0;i<=n;++i)
     dp[i][0]=1;
     for(int i=1;i<=n;++i)
     {
         for(int j=1;j<=sum;++j)
         {
             dp[i][j]=dp[i-1][j];//do not include 
             if(a[i-1]<=j)
             dp[i][j]+=dp[i-1][j-a[i-1]]; // include sum
         }
     }
     return dp[n][sum];
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    int k=ab.nextInt();
    int memo[][]=new int[n+1][k+1];
    System.out.println(fn(arr,n,k));
}
}
}

Read More