Guess the Number

Problem

Tags : GCD , LCM .

Idea : This is a simple problem . Just need to know gcd and lcm evaluation .

Given a string consisting Y and N .

First , you have to calculate the lcm of the position index of Y in the string .

If the lcm is divisible by any position index of N in the string, print -1 else print the lcm .

If there is no Y in the string , lcm is 1 .

My Solution

Euler Totient Function

Problem

Idea : The problem in very easy . Just straight forward approach if Euler Totient Function is needed .

You can learn Euler Totient Function from wiki .

Just take the input n and call phi function to calculate phi(n) . Then print it .

My Solution

Prince and Princess

Problem

Idea : Given two number sequence . You have to find out the LCS of the two . But you can not use the normal LCS finding algorithm .

You have to find out LCS using LIS . You can learn LIS from here

For a single sequence of number , we can calculate LIS as below -

Push the first element in a vector . Then , if the number is greater then the top element of the vector , push it also , else find out its position of the vector using binary search . Then put it in the position .

Then the LIS is the size of vector .

But for two sequence ?

We only take the element that are present in both sequence . To maintain increasing sequence , we may indexing the first sequence from 1 .

Then in second sequenec , we cheak whether it whether it present in first sequence or not . If it is not present , skip it . The first value that is present in both sequence , push it in a vector . Then if the index of next element is greater than the index of the last element of vector , push it . Else , find out the position of the index in the vector and put it .

Finally , the size of vector is our answer .

My Solution

Divide the Land

Problem

Idea : Given a trapezium . You have to divide the trapezium in two equal part of area . You have to draw a parallel line with the parallel line of the trapezium .

Consider the above trapezium . Given AB  ,CD , AD and BC . You have to find out AE and BF so that we can draw the parallel line joining E and F . Given trapeziums are as above . Where AB || CD and AB>CD .

Here , the area of ABFE = the area of CDEF = the area of trapezium ABCD / 2 .

The area of trapezium ABCD = ( AB + CD ) * h / 2 ------------------------ (1)

Here h is height and it is unknown .

We can draw a triangle combining the triangle AmD and BnC . The new triangle is pqr . We know its sides . pq = AB - CD , pr = AD and qr = BC . So we can calculate its area . Say it is triangleArea .
We know , area of triangle pqr , triangleArea  = pq * h / 2 .

                                              or , h= 2 * triangleArea / pq .

Putting the value of h in equation (1) , we may get the area of trapezium ABCD . Say it is trapeziumArea .

So , the area of ABFE = the area of CDEF = trapeziumArea / 2 .

Or , the area of CDEF = trapeziumArea / 2 = CD * n + triangle rst .
Or ,  CD * n +  b * n / 2 = A  .        --------------- (2)        Let , A =  trapeziumArea / 2 .

In the triangle pqr , rst and pqr are simillar triangle .

So , b / pq = n / h
So , b = n * pq / h

Putting the value of b in equation (2) ,

we get , CD * n + ( n * pq / h ) * n / 2 = A
       Or,  CD * n + pq * n * n / 2h = A
      Or , pq * n * n + 2h * CD * n - 2 * h * A = 0

So , n = ( -2h * CD + sqrt(( 2h * CD ) * ( 2h * CD) - 4 * pq * ( - 2A * h ) ) ) / ( 2 *pq )

In triangle AmD , n / h = DE / AD
                   So , DE = AD * n /h .
                   So , AE = AD - DE .

Similarly , in triangle MnC ,
                 n / h = CF / BC
            So , CF = BC * n / h
            So , BF = BC - CF .

And our answer is AE and BF .

My Solution

Vaishnav and Pizzas

Problem

Idea : Given an integer N . You have to find out the nuber of P/Q where gcd(P,Q) = 1 ,  P/Q<1 and P,Q can be up to N .

To do so , if we iterate P , Q up to N and try to cheak gcd , it must get TLE . Because N can be up to 10000 and the complexity is 10000*10000 will not pass within the given time limit . 

So , we need the help of Euler's Totient Function . You can learn Euler's Totient Function from wiki .
Euler's Totient Function gives the number of integer i(<n) that are co-prime to n . That means their gcd = 1 .

Euler's Totient Function gives output 1 for input 1 . But 1/1 = 1 .So we can avoid this . We can make P/Q by any co-prime/n(<1) . So for every value throw 2 to N returned by Euler's Totient Function is the possible couple of number . We can add these and our answer is this .

My Solution

Little Vaishnavi and plywood

Problem

Idea : For this problem , given the position of damaged wood m and the number of jump k that the damaged wood can tollarate over it .You have to count the number of jump until the damaged wood break down .

Here we have to handle the following cases-

1 . m = 1 and k = 0 or k>0
2 . m = 5 and k = 0 or k>0
3 . 1<m<5 and k is even or k is odd.

1 . If m = 1 , that means the damaged wood is in first position .
For that ,
If the value of k = 0 , we can not make any jump .
If the value of k is other than 0 ,
For this situation ,
If k=1 , Number of jump = 8
If k=2 , Number of jump =16
If k=n , Number of jump =8*n


2 . If m = 5 , that means the damaged wood is in last position .

For that ,
If the value of k = 0 , we can make 4 jumps .
If the value of k is other than 0 ,
For this situation ,
If k=1 , Number of jump =12
If k=2 , Number of jump =20
If k=n , Number of jump =8*n +4

3 .  If the value of m is not 1 and not 5 .

If k is even ,the number of jump is 4*k+(m-1)
If k is odd , the number of jump is 4*k+(5-m)

My Solution

Vaishnav and Factorials

Problem

Idea : Given an integer N . You have to do the following tasks-

1 . Calculate the factorial of  N .

2 . Count how many 4 or 7 are in N!

To do the first task -

You have to calculate N! . Very simple . Wait , the range of N from 1 to 250 . Using built in data type , you can calculate factorial up to 20 . Then ?

Now , you have to think something new . To face this situation , we can use array . In an array , we will keep a value . In every cell of the array , we will keep every digit of the value . Now think about calculating factorial as below -

                                         factorial = 1 ;
                                         for(int i=1;i<=N;i++)
                                         factorial*=i ;        // Multiplication to calculate factorial

For an array , we will multiply with array cell start from starting .

Initially we assign array[0] = 1 , and carry = 0 . Then for every value comes in the loop , we will multiply with every cell and add carry . Then the last digit of the value will remain in current position of the array . The carry is value/10 . After multiplying , we keep the carry infront of the array . Thus , if we iterate till N . We will get factorial in the array .

To do the second task -

Iterate from the starting of the array to the last and increase counter if array[i]==4 or array[i]==7 .

Then print the value of counter .

My Solution

Composite Numbers Having 7

Problem

Idea : Given two integer M and N where M<=N and the value of N would be up to 1000000 .

You have to do the following tasks -

1 . Find out the composite number C where M<=C<=N .

2 . Count the composite number containing digit 7 .

3 . If there is no composite number that contains 7 , print -1 else print the number of composite number that contains 7  . 

To do the first one , you can use sieve method to indicate the composite numbers .

Then for the second one , cheak every composite number . Whether it contains 7 or not .

If yes , increase counter .

And for the last one , if the value of counter is 0 , print -1 else print the counter .

My Solution

Small factorials

Problem

Idea : Given an integer n . You have to calculate n! . Very simple . Wait , the range of n from 1 to 100 . Using built in data type , you can calculate factorial up to 20 . Then ?

Now , you have to think something new . To face this situation , we can use array . In an array , we will keep a value . In every cell of the array , we will keep every digit of the value . Now think about calculating factorial as below -

                                         factorial = 1 ;
                                         for(int i=1;i<=n;i++)
                                         factorial*=i ;        // Multiplication to calculate factorial

For an array , we will multiply with array cell start from starting .

Initially we assign array[0] = 1 , and carry = 0 . Then for every value comes in the loop , we will multiply with every cell and add carry . Then the last digit of the value will remain in current position of the array . The carry is value/10 . After multiplying , we keep the carry infront of the array . Thus , if we iterate till n . We will get factorial in the array .


My Solution

Holes in the text

Problem

Idea : Given a string composed of uppercase letters .You have to count the hole in the string , specifically ,  an alphabet B contains 2 hole , A contains 1 etc .

Look , only alphabet B contains 2 hole . Alphabet A , D , O , P , Q and R are have 1 . Other have no hole . The summation of hole containing each alphabet in the given string is our answer .

My Solution

Factorial

Problem

Idea : Given an integer n , you have to find out number of zeros at the end of n! .

There are one zero at the end of a number x . What is its meaning ? That means , x can be expressed as multiple of 10(5*2) . Similarly , There are two zero at the end of a number x . What is its meaning ? That means , x can be expressed as multiple of 10(5*2)*10(5*2) . If we want to count the number of zero , we should count the number of 5*2 appears in the number . The number of zero is equal to the number of 5*2 .

To do so , we first look up at 5 and 2 . How many 5 and 2 is in the number .

As example , if n=10

Number of 5 = 10/5 = 2
Number of 2 = 10/2 = 5

We see that , the number of 2 > the number of 5 .

So , cheaking 5 is enough .

In an integer n , number of 5 is n/5 .

Some numbers have two , three or more munber of 5 as 25 , 50 , 75 , 100

So , we can cheak in n the total occurance of 5 by -

Single 5 = n/5
Double 5 = n/25
Triple 5 = n/75 and so on......

The total number of 5 = The total number of 5*2 = The total number of zero .


 My Solution

Enormous Input Test

Problem

Idea : Take input two integer n and k . Then again take input n long integer . Count the number of value those are divisible by k .

My Solution

ATM

Problem

Idea : It is an easy problem . Take input an integer x and a floating value Y . If the integer x is multiple of 5 and x+0.5 if less than or equal Y , print Y-(x+0.5) . Else print Y .

My Solution

Life, the Universe, and Everything

Problem

Idea : It is a very easy problem . Just for cheaking I/O knowledge .
Take integer as input and print that . When 42 is arrive , Stop .

My Solution

EmoticonsDiv2

Problem

Idea : Given emoticon number N and one emoticon . You have to make N emoticon by copy pasting the given emoticon . You have to determine the smallest number of action to reach N .

To do so , we think a function that gives minimum number of action for N .  Now see , we can copy paste only those imoticon whoose number are proper divisor of N . If  N = 1 , then we need 0 action to reach N . Because we have 1 emoticon given . It can be base case . For every divisor of N . We calculate the action number and take the minimum one .

My Solution

ChooseTheBestOne

Problem

Idea : Given a circle of people each having a t-shirt numbered from 1 to N . You have to find out the person with which t-shirt remain alive after playing  the discussed game in problem .

In this problem , we have to find out one , out of N . So , N-1 turn needed to eliminate N-1 people . In each turn t , people having t^3 called by shiny eliminate . After one elimination , we starts from the next person who was the next person of immediately eliminated . So , we need to start from the position . Each turn calling starts from 1 . So a person who is t^3 far from the current position will eliminate . So for every turn , we can find out the eliminated position by the formula :

                                E_Position = Current_position+t^3-1

The peoples are in circle and the counting may overlap . So , the formula will be :
                               
                                E_Position = ( Current_position+t^3-1 ) % Number_of_remaining_people .

My Solution

NumbersChallenge

Problem

Idea : You are given a number sequence and you have to find out the smallest number that can not be formed by the adding some combination of given integers .

To do so , we can evaluate all combination produced value . If the amount of given integer is N . Then 2^N combination is possible . We can use bitmask to make the values that produce the given integer sequence .

 We calculate those value and give true result for those values in a boolean array . Then iterating from first , we can easily find out the required value . 

My Solution

Monkey Banana Problem

Problem

Idea : Given a diamond shaped 2D array . You have to find out the maximum summation of weight of those cells of which cells form a road to upper cell to lower cell .

To do so , we consider the upper single cell . For this cell , the maximum summation is itself .
For the next two cell , calculate the maximum summation . From which cells , we can visit the cell , we take the maximum of those . Then we do so for next rows . That means , every cell has its maximum summation that is required as above . So , our result is at the last cell .

My Solution