Editorial : Coyote & ACME Bombs

Problem : Removing minimum element from every subarray and count all such subarrays whose sum is divisible by K.

Think over another simple problem of similar kind, without removing any element. That is count how many subarrays’ sum is divisible by K. Then only move forward!

Considering some subarray from some index L to some index R where L < R (strictly less). Suppose minimum element of this subarray is at index M where L <= M and M <= R . It is easy to observe that for the left subarray ([L,M-1]) and the right subarray ([M+1,R ]) will have their own minimum element independent of index M. Thus after solving the problem for any subarray, we have to divide the problem in 2 different independent parts. This will be done with the help of recursion (Divide & Conquer).

Now the issue is how to solve the problem for a particular subarray. In a subarray $[L,R]$ with minimum at index $M$, we have to consider these subarrays:-

  1. Subarrays starting at index M and going towards R
  2. Subarrays starting at index M and going towards L
  3. Subarrays starting at some index x less than M and completing at some index y greater than M. That is L<=x<M<y<=R.

Lets solve them one by one :-

  1. Remove the element at index M (bcoz v have to discard element at index M), that is start with element at index M+1 and traverse towards R adding elements one by one and checking at each step whether the sum is divisible by K or not. (can be done using modulo % operator).
  2. Similarly, Remove the element at index M, that is start with element at index M-1 and traverse towards L adding elements one by one and checking at each step whether the sum is divisible by K or not. (can be done using modulo % operator).
  3. This one is interesting. For finding these kind of subarrays, we could take help from the above two subarrays. Lets assume that there are u subarrays starting at index M and going towards index L having reminder r (when divided with K). Also say there are v subarrays starting at index M and going towards index R having reminder K-r. Each pair of these subarray also forms a subarray eligible to be counted. (Why ? If you merge two subarrays having reminder $2$ and $K-2$, the merged subarray will have reminder 0). Thus the answer would be u*v.

After solving for a subarray, one has to call two recursion calls. The time complexity of this problem would be like Quicksort where u divide the subrray into 2 segments and the extra time other than recursion is O(n) (bcoz u have to traverse each segment to save reminders into some map).

U will have to read the solution now after understanding these key points!

The link to the solution is

http://ideone.com/S5fPvC

If u have any queries or doubts, feel free to comment or contact our team!

OneMany or ManyOne Editorial

The link to problem is

https://www.hackerrank.com/contests/codestar-long-programming-contest/challenges/onemany-or-manyone

The question was pretty easy and straight forward if you have idea about hashtables or hashing. First of all an empty list or a list with only one number is always neither! For a list to be “OneMany”, there has to be atleast one number which occurs more than once i.e. its frequency should be greater than 1. For a list to be “ManyOne”, the size of hashtable should be greater than 1. If a list satisfies both above conditions, it is both! The code is very very simple and the link is :-

http://ideone.com/hNF9RP

“The most important property of a program is whether it accomplishes the intention of its user.”
― C.A.R. Hoare

Keep Coding

Manish M Berwani

Sorting in Java (Comparable v/s Comparators)

This post will help u if u have trouble with sorting class instances by different data fields. Also distinction between Comparable & Comparator Interfaces is show.

java.util.Arrays has many overloaded sorting methods. Simply if you want to sort any primitive type like int, boolean, char, long, double

java.util.Arrays.sort(arr);

where arr is array name!
It will use QuickSort for any primitive type.
What if the array of non-primitive type :-

Eg. Suppose you want to sort an array emp[] of type Employee class given below

public class Employee{
   int id,salary,yearOfJoining;
}

(The problem here is Arrays.sort() doesn’t know how to compare two Employees)

There are two ways according to the requirement :-

1. Comparable Interface

Comparable Interface has only one method

int compareTo(Object );

Arrays.sort() method implicitly calls compareTo(Object ) method when the array is of non-primitive type to compare two Objects.
So one just has to add an additional method to class definition.

Eg.

public class Employee{
   int id, salary, yearOfJoining;
   
   public Employee(int id,int salary,int yearofJoining){
      this.id = id;   this.salary = salary;    this.yearofJoining = yearofJoining;      
   }
   int compareTo(Object x){
      return this.id - ((Employee) x).id;
   }
}

public class Main{
   public static void main(String args[]){
      int n = 8;
      Employee es[n] = new Employee[n];
      for(int i=0;i&lt;n;i++){
          es[i] = new Employee(n-i,100000-i*1000,2011-i);
       }
      Arrays.sort(es);
   }
}


Arrays.sort() method will sort the array with respect to employees’ ids!

2. Comparator Interface

If one wants to sort by different data members, then one must use Comparators as shown below…

Comparator Interface also has only one method

int compare(Object , Object);

But the Use of Comparator is phenomenon. Suppose now you want to sort the given array with respect to their salaries or by their yearOfJoining.
One can’t write other compareTo() method.

Here the Comparator comes Handy!

Arrays.sort(Object arr[], Comparator obj)

is the method using different Comparators.

Eg.

public class Employee{
   int id, salary, yearOfJoining;
}

public class bySalary implements Comparator<Employee>{
   int compare(Employee one, Employee two){
      return one.salary-two.salary;
   }
}

public class byYearOfJoining implements Comparator<Employee>;{
   int compare(Employee one, Employee two){
      return one.yearOfJoining - two.yearOfJoining;
   }
}

When you want to sort by Salary

Arrays.sort(array, new bySalary<Employee>())

and when by yearOfJoining

Arrays.sort(array, new byYearOfJoining<Employee>())

This is because overloaded sort method expects a comparator object.
For non-primitive types Arrays.sort() method uses MergeSort to make sure the time complexity remains O(nlogn).


“The most important property of a program is whether it accomplishes the intention of its user.”

C.A.R. Hoare

Keep Coding

Manish M Berwani

Sorting by Inbuilt Functions in C

For competitive coding purposes, writing sorting code can be messy, full of bugs, and redundant.  There is no need of writing sorting algorithms because the most efficient of them are already implemented.

In C,Inbuilt QuickSort is availabe in <stdlib.h> under the signature


void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));

Where
base                 = void pointer towards the array to be sorted,
nitems            = number of elements in the array to be sorted
size                  = sizeof(“Your DataType“)
function ptr   = pointer towards a function returning an int by comparing two values.

The function type casts void pointer to required data type and returns the difference between values.

int cmpfunc (const void * p1, const void * p2)
{
   return ( *(int*)p1 - *(int*)p2 );
}

If cmpfunc returns:

  • < 0 The element pointed by p1 goes before the element pointed by p2
  • = 0 The element pointed by p1 is equivalent to the element pointed by p2
  • > 0 The element pointed by p1 goes after the element pointed by p2

This comparator function can be used to sort structures and unions also where one has to specify which data member of by what criteria comparison between two structure variable will be done!

Eg.

#include <stdio.h>;
#include <stdlib.h>;

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

void main(){
   int arr[] = {6,5,9,8,2,1,0,69,47,58,25,11,66,23}, i;
   qsort(arr,sizeof(arr),sizeof(arr[0]),cmpfunc);
   for(i=0;i<sizeof(arr);i++)
      printf("%d\n",arr[i]);
}

Output of this code is

0
1
2
5
6
8
9
11
23
25
47


“The most important property of a program is whether it accomplishes the intention of its user.”

C.A.R. Hoare

Keep Coding
Manish M Berwani