Page 1 of 1

Easy Coding Contest-9 Editorial

PostPosted: Sat Feb 25, 2017 2:32 pm
by BishalG
Problem A: Vely Easy Problem
Link: http://devskill.com/CodingProblems/ViewProblem/273
Problem Setter: Bishal Gautam

You are given string determine whether it contain 'r' or not
Idea: We may use boolean flag variable and make it 'false' initially.Then after iterating on string if we find 'r' character then makes
flag 'true'. so, finally if flag is true , we have to print "Vely easy" otherwise "Not vely easy".


Problem B: Find the Intersection
Link: http://devskill.com/CodingProblems/ViewProblem/272
Problem Setter: Jaber Kibria

Given S sets and distinct numbers in each set, find and print the numbers in their intersection.
Idea:
This problem is about string parsing and some maths. there is not mentioned how many elements are there in a particular set. So, we may use "stringstream" in c++ to parse string into integers.
Then, for every elemnts in the set way will increase counter in STL map for occurance.
Finally, iterating all possible elements, if we found counter is equal to N, then this element must be present in all set, eventually intersection of all set.


Problem C: Too Easy
Link: http://devskill.com/CodingProblems/ViewProblem/215
Problem Setter: Sifat Rabbi

You are given a number N upto 100000 digits. You have to find N modulo 100000.
Idea: You have to print last last 5 digits skiping printing any leading zeros. For this, if length of N is less than 5 directly output it without printing 0 at th begining and if length is greater than 5 ,just keep last 5 digits and do the same work. For skipping of printing of leading 0, you may use boolean flag variable.



Problem D: Divisor - Multiple
Link: http://devskill.com/CodingProblems/ViewProblem/190
Problem Setter: Feroz Ahmmed

Given two integers A and B. Find the number of values that are multiple of A and divisor of B.
Idea:
For multiple of A (say M=A*X ) to be divisor of B ( i.e B%(A*X)==0 ), B must be divisible by A.
So, if B is not divisible by A, then answer will be 0.
otherwise, we have total options which is equal to number of divisors of B/A .
So, answer will be number of divisors of B/A.
we can calculate numbers of divisors by iterating upto square root of (B/A). So, overall complexity is: O( TC*sqrt(B/A) ).



Problem E: Modified Golbach's Conjecture
Link: http://devskill.com/CodingProblems/ViewProblem/177
Problem Setter: Bakhtiar Hasan

Given N, in how many ways the number N can be written as sum of 1 or more primes.(N<=1000)
Idea:
We can solve this problem using Dynamic programming. For every Prime we have an option to include it in solution or Do not include it.
Lets suppose, we have sets of primes (about 170 ) as coins, we have to answer how many ways summation N can be formed using these coins. So, this is a variation of classic coin change problem.
Here, we can write a memorized recursive call of two states, that are- position of Prime taking currently(say P) and Summation made yet( Say S ). So, we may change state if we can take current prime : take current prime and update summation as long as valid summation i.e. (P, S+prime[P] ) or do not take current prime i.e ( P+1, S ).