Counting Sort

Comparison Sorting
Quick sort usually has a running time of n log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms arecomparison sorts, which means they sort a list just by comparing the elements with each other. A comparison sort algorithm cannot beat n log(n) (worst-case) running time, since that is the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).

Alternative Sorting
However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.

---

Challenge
Given a list of integers, can you count and output the number of times each value appears?

Hint: There is no need to sort the data, you just need to count it.

Input Format
There will be two lines of input:

• n - the size of the list
• ar - n numbers that makes up the list

Output Format
Output the number of times every number from 0 to 99 (inclusive) appears in the list.

Constraints
100 <= n <= 1000000
0 <= x < 100 , x ∈ ar

Sample Input

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33 

Sample Output

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2 

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99 

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int B[100];
int main() 
{
   long int n,i;
   scanf("%ld",&n);
   int A[n];
   for(i=0;i<n;i++)
        scanf("%d",&A[i]);
   
    for(i=0;i<n;i++)
        B[A[i]]+=1;
   
    for(i=0;i<100;i++)
        printf("%d ",B[i]);

             printf("\n\n");

    for(i=0;i<100;i++)
        while(B[i]--)
           printf("%ld ",i);

return 0;
}

Two arrays

You are given two integer arrays, A and B, each containing N integers. The size of the array is <= 1000. You are free to permute the order of the elements in the arrays.

Now for the real question - is there an arrangement of the arrays such that Ai+Bi>=K for all i where Ai denotes the ith element in the array A.

Input Format
The first line contains an integer T denoting the number of test-cases. T test cases follow. Each test case is given in the following format.

The first line contains two integers, N and K. The second line contains N integers separated by a single space, denoting A array. The third line describes B array in a same format.

Output Format
For each test case, if there is such arrangement exists output “YES”, otherwise “NO” (quotes for clarity).

Constraints
1 <= T <= 10
1 <= N <= 1000
1 <= K <= 109
0 <= Ai, Bi <= 109

Sample Input

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

Sample Output

YES
NO

Explanation

The first input has 3 elements in Array A and Array B, we see that the one of the arrangements, 3 2 1 and 7 8 9 has each pair of elements (3+7, 2 + 8 and 9 + 1) summing upto 10 and hence the answer is “YES”.

The second input has B array with three 3s. So, we need at least three numbers in A to be greater than 1. As its not the case, the answer is “NO”.

............................................................................................................
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int partition(long int A[],long int f,long int l)
{
long int i=f,j,x,temp;
x=A[l];
 for(j=f;j<l;j++)
 {
   if(A[j]<x)
   {
     temp=A[j];
     A[j]=A[i];
     A[i]=temp;
     i++;
   }
 }
    A[l]=A[i];
    A[i]=x;
return i;
}

void Sort1(long int A[],long int f,long int l)
{
 if(f<l)
 {
 long int q=partition(A,f,l);
 Sort1(A,f,q-1);
 Sort1(A,q+1,l);
 }  
}
int main() {
   int T,i;
    scanf("%d",&T);
    for(i=0;i<T;i++)
    {
      int N,i,j,k;
    long int K;
        scanf("%d %ld",&N,&K);
        long int A[N],B[N];
        for(j=0;j<N;j++)
            scanf("%ld",&A[j]);
        for(j=0;j<N;j++)
            scanf("%ld",&B[j]);
        
      Sort1(A,0,N-1);
      Sort1(B,0,N-1);
        k=N;
      for(i=0;i<N;i++,k--)
      {
        if(A[i]+B[k-1]<K)
        {
          printf("NO\n");
          break;
         }
       }
        if(i==N)
       printf("YES\n");
    }    
    
    return 0;
}

Filling Jars

Animesh has N empty candy jars numbered from 1 to N with infinite capacity. He performs M operations. Each operation is described by 3 integers a, b and k where a and b are index of the jars and k is the number of candies to be added inside each jar with index between a and b (both inclusive). Can you tell the average number of candies after M operations?

Input Format
The first line contains two integers N and M separated by a single space.
M lines follow. Each of the M lines contain three integers a, b and k separated by single space.

Output Format
A single line containing the average number of candies across N jars, rounded down to the nearest integer.

Constraints
3 <= N <= 107
1 <= M <= 105
1 <= a <= b <= N
0 <= k <= 106

Sample Input #00

5 3
1 2 100
2 5 100
3 4 100

Sample Output #00

160

Explanation
Initially each of the jar contains 0 candies

0 0 0 0 0  

First operation

100 100 0 0 0  

Second operation

100 200 100 100 100  

Third operation

100 200 200 200 100  

Total = 800, Average = 800/5 = 160

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int i,j;
    long int N,M,a,b,k,sum=0,c;
    scanf("%ld %ld",&N,&M);
    
    for(i=1;i<=M;i++)
    {
      scanf("%ld %ld %ld",&a,&b,&k);
     c=b-a+1;
     c=c*k;
     sum=sum+c;        
    }
    sum/=N;
    printf("%ld",sum);    
    return 0;
}

Harry Potter And The Floating Rocks

Famous wizard Harry Potter is stuck in a huge room and has to save Hermione Granger from a monster. Harry is at location P1 given by integral coordinates (x₁,y₁) and Hermione is at location P2 given by integral coordinates (x₂,y₂). Sadly P1 and P2 are the only points at which floating rocks are present. Rest of the room is without floor and underneath is hot lava.

Harry has to go from P1 to P2 but there are no floating rocks to walk on. Harry knows a spell that can make the rocks appear but only on the integral coordinates on the straight line joining P1 and P2.

How many rocks can appear at locations (x,y) on the line segment between P1 and P2 (excluding P1 and P2) which satisfy the condition that both x and y are integers?

Input Format
The first line contains a single integer T, the number of test cases. T lines follow.
Each of the following T lines contains one test case each. Each test case contains 4 integers x₁, y₁, x₂ and y₂ separated by a single space.

Output Format
A single line containing the number of rocks.

Constraints
1 <= T <= 10⁵
-10⁹ <= x₁, y₁, x₂, y₂ <= 10⁹

Sample input

3
0 2 4 0
2 2 5 5
1 9 8 16

Sample Output

1
2
6

Explanation

Case 1: As shown in the figure, between (0,2) and (4,0) there’s only 1 integral point (2,1) hence 1 rock.
Case 2: Between (2,2) and (5,5) lies (3,3) and (4,4), hence 2 rocks.
Case 3: Between (1,9) and (8,16) there lies 6 rocks at positions (2,10) (3,11) (4,12) (5,13) (6,14) (7,15).

..............................................................................................

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

long int gcd(long int a,long int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}

int main()
{

    long int t,x1,y1,x2,y2,a,b,ans;
    scanf("%ld",&t);
    while(t--)
    {
        scanf("%ld %ld %ld %ld",&x1,&y1,&x2,&y2);
        a=abs(x2-x1);
        b=abs(y2-y1);
        printf("%ld\n",gcd(a,b)-1);
    }

    return 0;
}

Insertion Sort - Part 2

In Insertion Sort Part 1, you sorted one element into an array. Using the same approach repeatedly, can you sort an entire unsorted array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an element with just the first element - that is already “sorted” since there’s nothing to its left that is smaller than it.

In this challenge, don’t print every time you move an element. Instead, print the array every time an element is “inserted” into the array in (what is currently) its correct place. Since the array composed of just the first element is already “sorted”, begin printing from the second element and on.

Input Format
There will be two lines of input:

• s - the size of the array
• ar - the list of numbers that makes up the array

Output Format
On each line, output the entire array at every iteration

Constraints
1<=s<=1000
-10000<=x<= 10000 , x ∈ ar

Sample Input

6
1 4 3 5 6 2

Sample Output

1 4 3 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 2 3 4 5 6 

Explanation
Insertion Sort checks the ‘4’ first and doesn’t need to move it, so it just prints out the array. Next, the 3 is inserted next to the 4 and the array is printed out. This continues one element at a time until the entire array is sorted.

Task
The method insertion Sort takes in one parameter: ar, an unsorted array. Use an Insertion Sort Algorithm to sort the entire array.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/* Head ends here */
void insertionSort(int ar_size, int *  ar) {
    int i,j,x;
    for(i=1;i<ar_size;i++)
    {
        x=ar[i];
        j=i;
       while(ar[j-1]>x && j>=1)
       {
        ar[j]=ar[j-1];
           j--;
       }
       ar[j]=x;
     for(j=0;j<ar_size;j++) 
       printf("%d ",ar[j]);
       printf("\n");
    }

    


}

/* Tail starts here */
int main(void) {
   
   int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) { 
   scanf("%d", &_ar[_ar_i]); 
}

insertionSort(_ar_size, _ar);
   
   return 0;
}

Mark and Toys

Mark and Jane are very happy after having their first kid. Their son is very fond of toys. Therefore, Mark wants to buy some toys for his son. But he has a limited amount of money. But he wants to buy as many toys as he can. So, he is in a dilemma and is wondering how he can maximize the number of toys he can buy. He has N items in front of him, tagged with their prices and he has only K rupees.

Now, you being Mark’s best friend have the task to help him buy as many toys for his son as possible.

Input Format
The first line will contain two inputs N and K, followed by a line containing N integers

Output Format
Maximum number of toys Mark can buy for his son.

Constraints
1<=N<=105
1<=K<=109
1<=price of any toy<=109

Sample Input

7 50
1 12 5 111 200 1000 10

Sample Output

4

Explanation

He can buy only 4 toys at most. These toys have the following prices: 1,12,5,10.

-------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define M 100
int partition(int A[],int f,int l)
{
int i=f,j,x,temp;
x=A[l];
 for(j=f;j<l;j++)
 {
   if(A[j]<x)
   {
     temp=A[j];
     A[j]=A[i];
     A[i]=temp;
     i++;
   }
 }
    A[l]=A[i];
    A[i]=x;
return i;
}

void Sort(int A[],int f,int l)
{
 if(f<l)
 {
 int q=partition(A,f,l);
 Sort(A,f,q-1);
 Sort(A,q+1,l);
 }  
}



void CountTotal(int A[],int N,int K)
{
    int total=0,count=-1,i;
    Sort(A,0,N-1);
    for(i=0;i<N;i++)
    {
        if(total<K)
        {
          total+=A[i];
          count++;
        }
        else 
        {
            printf("%d",count); break;
        }
    
    }
}
int main() 
{
   int A[M],K,i,N;
    scanf("%d %d",&N,&K);
    for(i=0;i<N;i++)
      scanf("%d",&A[i]);

    CountTotal(A,N,K);
    return 0;
}

FizzBuzz

Write a program that prints (to STDOUT) the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

The goal is to write the shortest code possible.

Scoring: Your score is (200 - number of characters in your source code)/10

#define f printf
main(){for(int i=1;i<=100;i++)(i%3!=0)&&(i%5!=0)?f("%d\n",i):((i%3==0&&i%5==0)?f("FizzBuzz\n"):((i%3==0)?f("Fizz\n"):f("Buzz\n")));}