collect the balls between two Roads

collect the balls between two Roads

  February 27, 2019    

---

Problem :

There are two parallel roads, each containing N and M buckets, respectively. Each bucket may contain some balls. bucket place in non decreasing order
The geek can change the road only at the point of intersection(which means, buckets with the same number of balls on two roads). Now you need to help Geek to collect the maximum number of balls.


Input:

1
5 5   // n , m
1 4 5 6 8
2 3 4 6 90

Output :110

Explanation:
here we start with 2 and switch road from 4 then again switch to 6
So 2+3+4+5+6+90 =110

Approach:

here we can use merge concept of mergesort so try to iterate list until common point and assign max value .

Consider case when more than 1 bucket has same balls :)



Code:

  public static long fn(int a[],int b[],int n,int m)
  {
      long first=0,second=0,res=0;
      int i=0,j=0;
      while(i<n&& j<m)
      {
          if(a[i]<b[j]){
              first+=a[i++];
          }
          else if(a[i]>b[j])
          {
              second+=b[j++];
          }
          else
          {
              res+=Math.max(first,second)+a[i];
              first=0;
              second=0;
              int temp=a[i];
              ++i;
              temp=b[j];
              ++j;
              while(i<n && a[i]==temp)
              res+=a[i++];
              while(j<m && b[j]==temp)
              res+=b[j++];
          }
      }
      while(i<n)
      {
          first+=a[i++];
      }
      while(j<m)
      {
         second+=b[j++];
      }
      res+=Math.max(first,second);
      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 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

TieRopes Solution

TieRopes Solution

  July 02, 2018    

---

Problem:

Idea is to use Greedy Approach and tie node of consecutive ropes.

Code:

public int solution(int k, int[] a) { int count=0; for(int i=0;i<a.length;++i) { if(a[i]>=k) { ++count; continue; } if(i+1<a.length) a[i+1]+=a[i]; } return count; }

Read More

Max sum path in two arrays

Max sum path in two arrays

  March 29, 2018    

---

Problem:

Given two arrays(sorted)
The function returns the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays.
Switch (one array to another )from common elements

Reference:
https://practice.geeksforgeeks.org/problems/max-sum-path-in-two-arrays/1




Idea is to use merge sort algorithm and maintain two sum for 1st and 2nd array.
When common element is found then we will add max sum from both the arrays to result.

   int maxPathSum(int ar1[], int ar2[])
   {
       int i,j,sum,isum,jsum;
       i=j=sum=isum=jsum=0;
       while(i<ar1.length && j<ar2.length)
       {
         if(ar1[i]==ar2[j])
         {
           sum+=Math.max(isum,jsum)+ar1[i];
           isum=jsum=0;
           ++i;++j;
         }
         else if(ar1[i]<ar2[j])
         {
           isum+=ar1[i++];
         }
         else
         jsum+=ar2[j++];
       }
       while(i<ar1.length)
       {
         isum+=ar1[i++];
       }
       while(j<ar2.length)
       {
         jsum+=ar2[j++];
       }
       return sum+Math.max(isum,jsum);
   }

Read More

N meetings in one room

N meetings in one room

  July 25, 2017    

---

Tag :
 java comparator,how to store 3 elements in map, array

Problem:

There is one meeting room. There are n meetings in the form of (S [ i ], F [ i ]) where S [ i ] is start time of meeting i and F [ i ] is finish time of meeting i

What is the maximum number of meetings that can be accommodated in the meeting room ?

Idea is to use greedy approach.

Sort array by their finish time and compare if next meeting's start time is greater than prev's end time then print its index;

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
static class meeting
{
int start,finish,id;
meeting(int number,int s,int f)
{
this.start=s;
this.finish=f;
this.id=number;
}
@Override 
public String toString()
{
return this.id+" ";
}
}
static class meet implements Comparator<meeting>
{
@Override
public int compare(meeting a,meeting b)
{
if(a.finish>b.finish)
return 1;
else if(a.finish<b.finish)
return -1;
else
{
if(a.start>b.start)
return 1;
else if(a.start<b.start)
return -1;
else
return 0;
}
}
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
List<meeting> lst=new ArrayList<meeting>();
 int n=ab.nextInt();
   int arr[]=new int[n];
   for(int i=0;i<n;i++)
   arr[i]=ab.nextInt();
   int arr2[]=new int[n];
   for(int i=0;i<n;i++)
   arr2[i]=ab.nextInt();
for(int i=0;i<n;i++)
{
lst.add(new meeting(i+1,arr[i],arr2[i]));
}
Collections.sort(lst,new meet());
System.out.print(lst.get(0));
meeting mt=lst.get(0);
int prev=mt.finish;
for(int i=1;i<n;i++)
{
mt=lst.get(i);
if(mt.start>prev)
{
System.out.print(mt);
prev=mt.finish;
}
}
 System.out.println();
 }}}

Read More

Pairs Hackerrank solution in java

Pairs Hackerrank solution in java

  June 28, 2017    

---

Problem :
count the number of pairs of integers whose difference is K.

Idea was to use two pointer algo which can do this task in O(n).

code:
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
       
        Scanner ab=new Scanner(System.in);
        int n=ab.nextInt();
        int k=ab.nextInt();
        int count=0;
        long arr[]=new long[n];
        for(int i=0;i<n;i++)
            arr[i]=ab.nextLong();
        Arrays.sort(arr);
        int i=0,j=1;
   
    while(j < n) {
        long diff = arr[j] - arr[i];
       
        if (diff == k) {
            count++;
            j++;
        } else if (diff > k) {
            i++;
        } else if (diff < k) {
            j++;
        }
    }
        System.out.println(count);
    }
}

Read More

Hackerland Radio Transmitters Java

Hackerland Radio Transmitters Java

  June 25, 2017    

---

Problem: https://www.hackerrank.com/challenges/hackerland-radio-transmitters


Idea is to sort the array and check for the location from where we can transmit to both side (left and right)

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] x = new int[n];
        for(int x_i=0; x_i < n; x_i++){
            x[x_i] = in.nextInt();
        }
        Arrays.sort(x);
        int count=0;
        int i=0;
        int loc;
        while(i<n)
        {
            count++;
            loc=x[i]+k;
            while(i<n && loc>=x[i]) i++;
            loc=x[--i]+k;
            while(i<n && loc>=x[i]) i++;
        }
        System.out.println(count);
    }
}

Read More

Maximize Toys Geeks Solution Optimized

Maximize Toys Geeks Solution Optimized

  June 08, 2017    

---

Problem : Given an integer depicting the amount with you. Maximize the number of toys you can have with K amount , arrays have cost of toys.

Solution : A greedy algo which first sorts the array and check for first i elements whose sum is less than k.

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
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 i=0;
   int count=0;
   int arr[]=new int[n];
   for(i=0;i<n;i++)
   arr[i]=ab.nextInt();
   Arrays.sort(arr);
   i=0;
   while(i<n && arr[i]<=k)
   {
      k-=arr[i++];
      count++;
   }
   System.out.println(count);
}
}
}

Read More

Minimum Notes Required for money N

Minimum Notes Required for money N

  May 22, 2017    

---

Problem :

Here we are having two integers n,k total money and no. of notes we can use 
We need to find out how much money we can have(Maximum with given denomination according to old indian currency) 

Output :

 Print remaining money

Explanation :

Here Greedy algorithm is used we are checking with maximum denomination and if money is greater then use denomination if not then check with lower denomination

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
int money[]={1,2,5,10,20,50,100,500,1000};
while(t-->0)
{
   int n=ab.nextInt();
   int k=ab.nextInt();
   int i=8;
   while(n>0 && k-->0)
   {
       if(n>=money[i])
       {
           //System.out.println("salary "+n+" used denomination "+money[i]+" k"+k);
           n-=money[i];
         
       }
       else
       {
       if(i>0)
       {
       i--;
       k++;
       }
       }
      // System.out.println("Value of i "+i);
   }
   System.out.println(n);
}
}
}

Read More