Given three integers A, B and K. Initially, the first person was ahead of the second person by K kms. In every hour, the first person moves ahead by A kms and the second person moves ahead by B kms. The task is to print the number of hours after which the second person crosses the first. If it is impossible to do so then print -1.
Examples:
Input: A = 4, B = 5, K = 1
Output: 2
Initially, the first person was ahead by 1 km.
After 1st hour the first and second person are at the same place.
After 2nd hour the first person moves ahead of the first person by 1 km.Input: A = 6, B = 5, K = 1
Output: -1
A naive approach is to linearly check for every hour and print the n-th hour when the second person moves ahead of the first person.
An efficient approach is to solve the problem mathematically. The number of hours will be K / (B – A) + 1 when the second person moves ahead of the first person. Since you need to cover K kms, hence the time taken will be K / (B – A) where B – A is the speed of the second person with respect to the first person. If A ? B then it is not possible for the second person to cross the first person.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to return the number of// hours for the second person to move aheadint findHours(int a, int b, int k){ if (a >= b) return -1; // Time taken to equalize int time = k / (b - a); // Time taken to move ahead time = time + 1; return time;}// Driver codeint main(){ int a = 4, b = 5, k = 1; cout << findHours(a, b, k); return 0;} |
Java
// Java implementation of the above approachimport java.io.*;class GFG{ // Function to return the number of// hours for the second person to move aheadstatic int findHours(int a, int b, int k){ if (a >= b) return -1; // Time taken to equalize int time = k / (b - a); // Time taken to move ahead time = time + 1; return time;}// Driver codepublic static void main (String[] args) { int a = 4, b = 5, k = 1; System.out.println (findHours(a, b, k));}}// The code is contributed by ajit..@23 |
Python3
# Python3 implementation of the above approach# Function to return the number of# hours for the second person to move aheaddef findHours(a, b, k): if (a >= b): return -1 # Time taken to equalize time = k // (b - a) # Time taken to move ahead time = time + 1 return time# Driver codea = 4b = 5k = 1print(findHours(a, b, k))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approachusing System;class GFG{ // Function to return the number of// hours for the second person to move aheadstatic int findHours(int a, int b, int k){ if (a >= b) return -1; // Time taken to equalize int time = k / (b - a); // Time taken to move ahead time = time + 1; return time;}// Driver codestatic public void Main (){ int a = 4, b = 5, k = 1; Console.Write(findHours(a, b, k));}}// The code is contributed by ajit. |
Javascript
<script>// Javascript implementation of the above approach// Function to return the number of hours // for the second person to move aheadfunction findHours(a, b, k){ if (a >= b) return -1; // Time taken to equalize let time = k / (b - a); // Time taken to move ahead time = time + 1; return time;}// Driver codelet a = 4, b = 5, k = 1;document.write(findHours(a, b, k));// This code is contributed by Mayank Tyagi</script> |
2
Time Complexity: O(1), since there is a basic arithmetic operation that takes constant time.
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
