Say, I have an O(n^2) or O(n^3) solution to a problem . If I use the modulo operator in most of the statements inside the loops, will my program slow down ? With which factor will it slow down ? like 2*x,3*x,.. ? (if "x" is the execution time of the program when no modulo is used)

We are given a rooted tree with 'n' vertices, where , n<=10^5.

For the problem : Count the number of paths in a tree with sum=k .

I don't know its efficient solution.

And now the new problem is : —

Count the number of pair of paths in a rooted tree with sum=k.

Example, say the path(2-5) in a tree has sum=8, and another path (7-9) in the same tree has sum=9.

So the pair of paths:- {(2-5),(7-9)} has a sum=8+9=17.

Can I get some ideas on how to solve both of these problems ?

We are given a sequence : [1,2,...N]. Lets consider all the permutations of the above sequence. Now, a good permutation is defined as the one in which there is atleast one pair of numbers such that a[i]+1=a[i+1]. How to count the number of good permutations ? This problem is from some old contest.

This is a problem from a past hiring contest of Hackerrank. We are given an array which contains at max 10^4 elements. Total cost is defined as the sum of absolute difference of the old value of the element and the new value of the element.

Ex: 10 6 3 2 2000

Minimum Cost: 11

1st element 10 can be changed to 6. Cost = abs(10 — 6) = 4.

3rd element 3 can be changed to 6. Cost = abs(3 — 6) = 3.

4th element 2 can be changed to 6. Cost = abs(2 — 6) = 4.

So total cost = 11

Range of elements: [1, 10^9]

How can I apply dynamic programming to solve it? Thanks :-)

Thanks :)