About Code N Solve

Code N Solve

Strange Grid

Posted on March 1, 2015 by Code N Solve

A strange grid has been recovered from an old book. It has 5 columns and infinite number of rows. The bottom row is considered as the first row. First few rows of the grid are like this:

…………..

20 22 24 26 28

11 13 15 17 19

10 12 14 16 18

1 3 5 7 9

0 2 4 6 8

The grid grows upwards forever!

Your task is to find the integer in cth column in rth row of the grid.

Input Format

There will be two integers r and c separated by a single space.

Constraints

1≤r≤2 * 109

1≤c≤5

Rows are indexed from bottom to top and columns are indexed from left to right.

Output Format

Output the answer in a single line.

Sample Input

6 3

Sample Output

Explanation

The number in the 6th row and 3rd column is 25.

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

int main() {
    long long  int r,c,num;
    scanf("%lld%lld",&r,&c);
    if(r%2 == 0)
        {
        num =   10*((r/2)-1)+1;
        num = num + 2*(c-1);
    }
    else
        {
        num =   10*(r/2);
        num = num + 2*(c-1);        
    }
    printf("%lld\n",num);
    return 0;
}

Compile & Run : https://ideone.com/cp30GN

Connecting Towns

Posted on February 27, 2015 by Code N Solve

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4…Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note
Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn.
For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.

Input Format
The first line contains an integer T, T test-cases follow.
Each test-case has 2 lines. The first line contains an integer N (the number of towns).
The second line contains N – 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

Output Format
Total number of routes from T1 to Tn modulo 1234567
http://en.wikipedia.org/wiki/Modular_arithmetic

Constraints
1 <= T<=1000
2< N <=100
1 <= Ni <=1000

Sample Input

2
3
1 3
4
2 2 2

Sample Output

3
8

Explanation
Case 1: 1 route from T1 to T2, 3 routes from T2 to T3, hence only 3 routes.
Case 2: There are 2 routes from each city to the next, at each city, Gandalf has 2 choices to make, hence 2 * 2 * 2 = 8.

#include
#include
#include
#include

int main() {
    int T,N,v_in,route;
    scanf("%d",&T);
    while(T--)
        {
        scanf("%d",&N);
        N -= 1;
        route =1;
        while(N--)
            {
            scanf("%d",&v_in);
            route = (route*v_in)%1234567;
        }
        printf("%d\n",route);
    }
    return 0;
}

Compile & Run : https://ideone.com/1SpQ5T

Intro To Counting Sort Problem

Posted on February 27, 2015 by Code N Solve

Comparison Sorting
Quicksort 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 are comparison sorts, i.e., they sort a list just by comparing the elements with one another. A comparison sort algorithm cannot beat n log(n) (worst-case) running time, since n log(n) represents 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 space separated 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 <= 106
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

Explanation

the output states that 0 appears 0 times.
1 appears 2 times.
2 appears 0 times.
and so on in the given input array.

#include 
#include 
#include 
#include 

int main() {

    int N,i,arr[100]={0},V;
    scanf("%d",&N);
    while(N--)
        {
        scanf("%d",&V);
        arr[V] +=1;
    }
    for(i=0;i<100;i++)
        {
        printf("%d ",arr[i]);
    }
    return 0;
}

Intro To Sort

Posted on February 27, 2015 by Code N Solve

#codeifyoucansolve
There will be three lines of input:

V – the value that has to be searched.
n – the size of the array.
ar – n numbers that make up the array.

Output Format
Output the index of V in the array.

{The next section describes the constraints and ranges of the input. You should check this section to know the range of the input. }

Constraints
1<=n<=1000
-1000 <=x <= 1000 , x ∈ ar

{This “sample” shows the first input test case. It is often useful to go through the sample to understand a challenge. }

Sample Input

4
6
1 4 5 7 9 12

Sample Output

Explanation
V = 4. The value 4 is located at the 1st index in the array, so the answer is 1.

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

int main() {
    int N,K,V_arr,i;
    scanf("%d",&K);
    scanf("%d",&N);
    i=0;
    while(i<N)
        {
        scanf("%d",&V_arr);
        if(V_arr==K)
            printf("%d\n",i);
        i++;
    }
    return 0;
}

https://twitter.com/codeifucansolve

Handshake

Posted on February 27, 2015 by Code N Solve

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of Board of Directors of Acme.

Output Format

Print the number of handshakes for each test-case in a new line.

Constraints

1 <= T <= 1000
0 < N < 106

Sample Input

2
1
2

Sample Output

0
1

Explanation

Case 1 : The lonely board member shakes no hands, hence 0.
Case 2 : There are 2 board members, 1 handshake takes place.

#include 
#include 
#include 
#include 

int main() {

    int T,N;
    scanf("%d",&T);
    while(T--)
        {
        scanf("%d",&N);
        printf("%d\n",((N*(N-1))/2));
    }
    return 0;
}

Compiled & Run : http://ideone.com/SDF6T0

Minimum Draws

Posted on February 27, 2015 by Code N Solve

Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer after which he finds a matching pair?

Input Format
The first line contains the number of test cases T.
Next T lines contains an integer N which indicates the total pairs of socks present in the drawer.

Output Format
Print the number of Draws (x) Jim makes in the worst case scenario.

Constraints
1 <= T <= 1000
0 < N < 106

Sample Input

2
1
2

Sample Output

2
3

Explanation
Case 1 : A pair of socks are present, hence exactly 2 draws for the socks to match.
Case 2 : 2 pair of socks are present in the drawer. The first and the second draw might result in 2 socks of different color. The 3rd socks picked will definitely match one of previously picked socks. Hence, 3.

#include 
#include 
#include 
#include 

int main() {

    int T,N;
    scanf("%d",&T);
    while(T--)
        {
        scanf("%d",&N);
        printf("%d\n",N+1);
    }
    return 0;
}

Run & Compiled : http://ideone.com/MsfvXh

Lonely Integer

Posted on February 27, 2015 by Code N Solve

Problem Statement

There are N integers in an array A. All but one integer occur in pairs. Your task is to find out the number that occurs only once.

Input Format

The first line of the input contains an integer N indicating the number of integers.
The next line contains N space separated integers that form the array A.

Constraints

1 <= N < 100
N % 2 = 1 ( N is an odd number )
0 <= A[i] <= 100, ∀ i ∈ [1, N]

Output Format

Output S, the number that occurs only once.

Sample Input:1

1
1
Sample Output:1

1
Sample Input:2

3
1 1 2
Sample Output:2

2
Sample Input:3

5
0 0 1 2 1
Sample Output:3

2
Explanation

In the first input, we see only one element (1) and that element is the answer.
In the second input, we see three elements, 1 exists at two places. The element that occurs only once is 2.
In the third input, we see five elements. 1 and 0 exist at two places. The element that occurs only once is 2.

#include 
#include 
#include 
#include 
#include 
int lonelyinteger(int a_size, int* a) {
    int sum=0,i,j;
    if(a_size %2 == 0)
        return 0;    
    for(i=0;i<a_size;i++)
        sum +=a[i];
    for(i=0;i<a_size;i++)
        {
        if((sum-a[i])%2==0 && a[i] !=0)
            {
            for(j=i+1;j<a_size;j++)
                {
                if(a[i]==a[j])
                    break;
            }
            if(j==a_size)
               return a[i];
        }  
    }
return 0;

}
int main() {
    int res;
    
    int _a_size, _a_i;
    scanf("%d", &_a_size);
    int _a[_a_size];
    for(_a_i = 0; _a_i < _a_size; _a_i++) { 
        int _a_item;
        scanf("%d", &_a_item);
        
        _a[_a_i] = _a_item;
    }
    
    res = lonelyinteger(_a_size, _a);
    printf("%d", res);
    
    return 0;
}
Compiled & Run : http://ideone.com/gLHC74

The Longest Common Subsequence

Posted on February 15, 2015 by Code N Solve

#codeifyoucansolve
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.

Given two sequence of integers, A=[a1,a2,…,an] and B=[b1,b2,…,bm], find any one longest common subsequence.

In case multiple solutions exist, print any of them. It is guaranteed that at least one non-empty common subsequence will exist.
Input Format

First line contains two space separated integers, n and m, where n is the size of sequence A, while m is size of sequence B. In next line there are n space separated integers representing sequence A, and in third line there are m space separated integers representing sequence B.

n m
A1 A2 … An
B1 B2 … Bm

Constraints

1≤n≤100
1≤m≤100
0≤ai<1000,where i∈[1,n]
0≤bj<1000,where j∈[1,m]

Output Format

Print the longest common subsequence and each element should be separated by at least one white-space. In case of multiple answers, print any one of them.

Sample Input

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

Sample Output

1 2 3

Explanation

There is no common subsequence with length larger than 3. And “1 2 3”, “1 2 1”, “3 4 1” are all correct answers.

Tested by Khongor

Solved score: 49.50pts
1433 hackers have submitted code

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void lcs(int N,int M,int m[],int n[])
{
    int L[M+1][N+1],i,j,k;
    for(i=0;i<=M;i++)
        {
        for(j=0;j<=N;j++)
            {
            if(i==0 || j==0)
                L[i][j]=0;
            else if(m[i-1]==n[j-1])
                L[i][j]=1+L[i-1][j-1];
             else
                {
                if(L[i-1][j]>L[i][j-1])
                    {
                    L[i][j]=L[i-1][j];
                }
                else
                    {
                    L[i][j]=L[i][j-1];
                }
            }
        }
    }
    k=L[M][N];
    int l[k];
    i=M;j=N;
    while(i>0&&j>0)
        {
        if(m[i-1]==n[j-1])
            {
         // printf("%d ",m[i-1]);
            l[k-1]=m[i-1];
            i--;j--;k--;
        }
        else if(L[i-1][j]>L[i][j-1])
            i--;
        else
            j--;
    }
    for(i=0;i<L[M][N];i++)
       printf("%d ",l[i]); 
    printf("\n");
}
int main() {

    int N,M,m[100],n[100];
    int i,j;
    scanf("%d%d",&N,&M);
    for(i=0;i<N;i++)
        scanf("%d",&n[i]);
    for(i=0;i<M;i++)
        scanf("%d",&m[i]);
    lcs(N,M,n,m);
    return 0;
}

Compiled :
http://ideone.com/F2Rgoy

The Longest increasing subsequence

Posted on February 10, 2015 by Code N Solve

#codeifyoucansolve
The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in ascending order. For example, the length of the LIS for { 15, 27, 14, 38, 26, 55, 46, 65, 85 } is 6 and the longest increasing subsequence is {15, 27, 38, 55, 65, 85}.
In this challenge you simply have to find the length of the longest strictly increasing sub-sequence of the given sequence.

Input Format

In the first line of input, there is a single number N.
In the next N lines input the value of a[i].

Constraints
1 ≤ N ≤ 106
1 ≤ a[i] ≤ 105

Output Format

In a single line, output the length of the longest increasing sub-sequence.

Sample Input

5
2
7
4
3
8

Sample Output

Explanation

{2,7,8} is the longest increasing sub-sequence, hence the answer is 3 (the length of this sub-sequence).

#include <stdio.h>
#define MAX 1000000
long int a[MAX],l[MAX];
int main() {

    long long int N,i,j,max;
   scanf("%lld",&N);
    i=0;
   while(i<N)
       {
       scanf("%ld",&a[i++]);
   }
   l[0]=1;
   if(N==1)
       {
       printf("%ld\n",a[0]);
       return 0;
   }
    max = 0;
   for(i=1;i<N;i++)
       {
       for(j=0;j<i;j++)
           {
           if((a[j]<a[i])&&(l[i]<l[j]+1))
             {
               l[i]=l[j];
           }
       }
       l[i] = l[i] + 1;
         if(max<l[i])
           {
              max = l[i];
         }  
   }
  /*  max =   0;
   for(i=0;i<N;i++)
       {
       if(max<l[i])
           max  =   l[i];
   }*/
   printf("%lld\n",max);
   return 0;
}

Compiled :

http://ideone.com/VtDbul

Knapsack

Posted on February 8, 2015 by Code N Solve

#codeifyoucansolve
Given a list of n integers, A={a1,a2,…,an}, and another integer, k representing the expected sum. Select zero or more numbers from A such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum (k).

Note

Each element of A can be selected multiple times.
If no element is selected then the sum is 0.
Input Format

The first line contains T the number of test cases.
Each test case comprises of two lines. First line contains two integers, n k, representing the length of list A and expected sum, respectively. Second line consists of n space separated integers, a1,a2,…,an, representing the elements of list A.

Constraints
1≤T≤10
1≤n≤2000
1≤k≤2000
1≤ai≤2000,where i∈[1,n]
Output Format

Output T lines, the answer for each test case.

Sample Input

2
3 12
1 6 9
5 9
3 4 4 4 8
Sample Output

12
9
Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

#include
int knapsack(int K,int w[],int v[],int n)
{
int i,k;
int t[n+1][K+1];
for(i=0;i<=n;i++)
{
for(k=0;k<=K;k++)
{
if(i==0||k==0)
t[i][k]=0;
else if(w[i-1]t[i-1][k])
{
t[i][k] = w[i-1]+t[i-1][k-w[i-1]];
}
else
{
t[i][k] = t[i-1][k];
}
}
else
t[i][k]=t[i-1][k];
}
}
return t[n][K];
}
int main() {
int T,N,n,K,num;
int w[2000],v[2000];
int k,j,i;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d”,&N,&K);
i=N;
k=0;
while(i–)
{
j=1;
n=K;
scanf(“%d”,&num);
while(n)
{
v[k]=j;
w[k]=num*j;
k=k+1;
j=j+1;
n=K/(num*j);
}
}
printf(“%d\n”,knapsack(K,w,v,k));
/*for(j=0;j<k;j++)
{
printf("%d %d\n",w[j],v[j]);
}*/
}
return 0;
}

Compiled & Run

http://ideone.com/4Ql8dB
https://twitter.com/codeifucansolve

Code N Solve

#codensolve #algorithms #datastructures

Author Archives: Code N Solve

About Code N Solve

Strange Grid

Connecting Towns

Intro To Counting Sort Problem

Intro To Sort

Handshake

Minimum Draws

Lonely Integer

The Longest Common Subsequence

The Longest increasing subsequence

Knapsack

About Code N Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve

Code If You Can Solve