CODEWITHSUNDEEP
c++
user2795662
user2795662

Reputation: 33

Returning a large number in C++

I am a beginner programmer and am trying out the Codility frog jump question. Here is my code solution: 

int solution(int, int, int, unsigned long int&);

int main(){

    unsigned long int stepsTaken = 1;

    int x = 10;
    int y = 85;
    int d = 30;

    solution(x, y, d, stepsTaken);

    cout << "Total Steps Taken: " << stepsTaken << endl;
}

int solution( int X, int Y, int D, unsigned long int &stepsTaken) {

    int currentPosition = X;
    int positionToGetTo = Y;
    int stepsJumpedEachTime = D;

    currentPosition += stepsJumpedEachTime;

    if(currentPosition < positionToGetTo){

        stepsTaken++;
        solution(currentPosition, positionToGetTo, stepsJumpedEachTime, stepsTaken);
    }

    return stepsTaken;
}

Now the problem I am having is when I attempt to fullfil the requirements to deal with a number range from 1-1000000000. If I change int y above to say 2000000 I get a negative returned. unsigned long int should return a positive number but when I use 2000000 it returns negative.

Upvotes: 0

Views: 3974

Answers (8)

Arif Basri
Arif Basri

Reputation: 11

100% score - C code :Codility: FrogJmp

int solution(int X, int Y, int D) {
    // write your code in C90
    if (Y == X) 
      return 0;
    else
      return (((Y - X) / D) + (((Y - X) % D) > 0 ? 1 : 0));     
}

expected worst-case time complexity is O(1) means no iteration...

Upvotes: 0

agnor
agnor

Reputation: 369

Solution using ceil:

#include <cmath>
#include <climits>

int solution(int X, int Y, int D) 
{
    if (X >= Y)
        return 0;

    if (D == 0)
        return INT_MAX;

    return std::ceil((double)(Y - X) / D);
}

Upvotes: 0

testoftiramisu
testoftiramisu

Reputation: 1

C solution. 100 out of 100 points on Codility

int FrogJmp(int X, int Y, int D) {

    int result = 0;
    int dest = Y - X;
    result = dest / D;

    if (dest % D != 0) {
        result++;
    }
    return result;
}

Upvotes: 0

Damien Garrido
Damien Garrido

Reputation: 158

A 100% "float" version which is about three times faster on my x64 CPU than the "int" version:

#include <cmath>

int solution(int X, int Y, int D)
{
    return std::floor( (double)( Y - 1 - X ) / D + 1 );
}

Upvotes: 0

user3287911
user3287911

Reputation: 1

I hope this will work:

class Solution {
    public int solution(int X, int Y, int D) {
    if(X>=Y)
    return 0;
    if((Y-X)%D!=0) return (Y-X)/D+1;
    else
    return (Y-X)/D;
   }
}

Upvotes: 0

user2873383
user2873383

Reputation: 21

Iteration takes too long.

int destination = Y - X;
int steps = destination / D;
int remainder = destination % D;
if (remainder != 0){
    steps++;
}
return steps;

Upvotes: 2

user2795662
user2795662

Reputation: 33

Got this to work without using recursion as follows:

#include <iostream>
#include <iostream>

using namespace std;

unsigned long int solution( int currentPosition,int positionToGetTo ,int       stepsJumpedEachTime);

int main(){

int x = 10;
int y = 1000000000;
int d = 30;

unsigned long int stepsTaken = solution(x, y, d);

cout << "Total Steps Taken: " << stepsTaken << endl;
}

unsigned long int solution(int currentPosition, int positionToGetTo ,int   stepsJumpedEachTime){

unsigned long int stepsTaken = 1;

currentPosition += stepsJumpedEachTime;

while (currentPosition < positionToGetTo){

    currentPosition += stepsJumpedEachTime;
    stepsTaken++;

}

return stepsTaken;

}

Upvotes: 1

Yulia V
Yulia V

Reputation: 3559

This happens because int numbers in C++ have limits - see http://www.cplusplus.com/reference/climits/. In most cases, standard types should satisfy your needs.

If no standard type is big enough, see What's the best (for speed) arbitrary-precision library for C++?

Here is a simpler version of your code, what do you think?

unsigned long int solution( int currentPosition, int positionToGetTo , int stepsJumpedEachTime) {

    if (currentPosition >= positionToGetTo)
        return 0; 

    return 1 + solution(currentPosition + stepsJumpedEachTime, positionToGetTo, stepsJumpedEachTime);

}

int main(){

    int x = 10;
    int y = 85;
    int d = 30;

    unsigned long int stepsTaken = solution(x, y, d);

    cout << "Total Steps Taken: " << stepsTaken << endl;
}

Upvotes: 2

Related Questions