Thursday 8 August 2013

Sum of Slope of all the number between given range


You are given range of number (A to B) and you have to tell the sum of slope of all the number between A and B.

Now we define the term slope of a number N. Slope of a number N is the number of digits (excluding the first and the last digit) which
is either maxima or minima in that number.

Consider a number N. A digit in number N is called minima if it is smaller than both of its neighbour and a digit is called maxima if it is larger than both of its neighbour.

In case of wrong ranges or unexpected ranges, please return  output as -1

Example 1 : Consider the range 1-100 in this range all the numbers are either one digit or 2 digit so the slope value of all the number is zero and hence the sum is zero.
Similarly, consider the range 100-150 the sum of slope of all the number in this range is 19

Example 2 : Consider the number 54698 in range 54698-54800. In this number 4 is a minima because it is smaller than it both neighbor i.e. 5 and 6. similarly digit 9 is a maxima because it is grater than both of its neighbor i.e. 6 and 8.

Slope of 54698 is 2 because it has 4 as minima and 9 as maxima and there is no other minima or maxima.

Similarly we check next numbers in the range 54698-54800 and sum of slope of all the numbers will be the output.


Solution:


class SumOfSlopeOfAllNumberBetweenAandB{
static int findSlope(int a, int b){
int sum = 0;
for(int i = a; i <=b; i++){
sum += slope(i);
}
return sum;
}

static int slope(int number){
int prev, sum = 0, current, next;
prev = number % 10;
number /= 10;
current = number % 10;
number /= 10;

if(number <=0 )
return 0;

while(number > 0){
next = number % 10;
number = number / 10;

if( (current > prev && current > next) || (current < prev && current < next))
                       sum++;
prev = current;
current = next;
}
return sum;
}

public static void main(String... args){
int a = 100, b = 150;
int slope = findSlope(a, b);
System.out.println(slope);
}
}

2 comments:

  1. I assume that to be challenging, this problem would have constraints that prevent you from solving it using this brute-force approach. Your algorithm is roughly exponential in the number of digits (or roughly linear in the numeric value) of b-a. This could be more challenging if you're expected to give a solution that is closer to linear in the number of digits.

    ReplyDelete
    Replies
    1. If I will find any better solution than this then I will update the post.

      If you want to share more information about the same then please comment.

      Delete