Given two numbers X and Y. the task is to find the number N (N ? 10^18) which satisfies these two conditions:
- (N + X) is divisible by Y
- (N – Y) is divisible by X
Examples:
Input: X = 18, Y = 42
Output:780Input: X = 100, Y = 200
Output: 300
Naive Approach/Brute Force Approach:
When constraints are small, then we can use this approach:
In this code, we define a function FindN that takes two integers X and Y as input and returns an integer N that satisfies the two conditions given in the problem. Inside the function, we use a while loop to iterate through all possible values of N until we find a solution or until N exceeds the upper limit of 10^18. For each value of N, we check if both conditions are satisfied using the modulo operator %. If both conditions are satisfied, we return the value of N. If no solution is found, we return -1.
In the main function, we define the values of X and Y and call the FindN function to compute the value of N. The computed value of N is then printed to the console.
Below is the implementation of the above approach:
C++
#include <iostream>using namespace std;#define int long long int// Function to find Nint FindN(int x, int y){ int N = max(x, y); // Loop through all possible values of N while ( N <= 1000000000000000000) { // loop until N <= 10^18 if ((N + x) % y == 0 && (N - y) % x == 0) { // check if both conditions are // satisfied return N; // return the value of N if a solution // is found } N++; // increment N } return -1; // return -1 if no solution is found}// Driver codesigned main(){ int X = 18, Y = 42; // Function call cout << FindN(X, Y); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main { static long findN(long x, long y) { long N = Math.max(x, y); // Loop through all possible values of N while (N <= 1000000000000000000L) { // loop until N // <= 10^18 if ((N + x) % y == 0 && (N - y) % x == 0) { // check if both conditions // are satisfied return N; // return the value of N if a // solution is found } N++; // increment N } return -1; // return -1 if no solution is found } public static void main(String[] args) { long X = 18, Y = 42; // Function call System.out.println(findN(X, Y)); }}// Contributed by adityasha4x71 |
Python3
def FindN(x, y): N = max(x, y) while N <= 10**18: if (N + x) % y == 0 and (N - y) % x == 0: return N N += 1 return -1# Driver codeX, Y = 18, 42print(FindN(X, Y)) |
C#
using System;namespace ConsoleApp{ class Program { static long FindN(long x, long y) { long N = Math.Max(x, y); // Loop through all possible values of N while (N <= 1000000000000000000) { // check if both conditions are satisfied if ((N + x) % y == 0 && (N - y) % x == 0) { return N; // return the value of N if a solution is found } N++; // increment N } return -1; // return -1 if no solution is found } static void Main(string[] args) { long X = 18, Y = 42; // Function call Console.WriteLine(FindN(X, Y)); } }} |
Javascript
function findN(x, y) { let N = Math.max(x, y); // Loop through all possible values of N while (N <= 1000000000000000000) { // Check if both conditions are satisfied if ((N + x) % y === 0 && (N - y) % x === 0) { return N; // Return the value of N if a solution is found } N++; // Increment N } return -1; // Return -1 if no solution is found}const X = 18, Y = 42;// Function callconsole.log(findN(X, Y)); |
150
Time Complexity: O(1018)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved based on the following idea:
We can implement the simple math concept of the number system.
- N + X = Y …………(i)
- N – Y = X …………(ii)
Normalizes the equation we can get N may be equal to (X*Y – X + Y). Also, it is satisfying these two conditions. So, the answer is (X * Y – X + Y).
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <iostream>using namespace std;#define int long long int// Function to find Nint FindN(int x, int y){ // Mathematical equation from approach int N = (x * y) - x + y; // Return N return N;}// Driver codesigned main(){ int X = 18, Y = 42; // Function call cout << FindN(X, Y); return 0;} |
Java
// Java code for the above approachimport java.util.* public class Main { // Function to find N public static int FindN(int x, int y) { // Mathematical equation from approach int N = (x * y) - x + y; // Return N return N; } public static void main(String[] args) { int X = 18, Y = 42; // Function call System.out.println(FindN(X, Y)); }}// This code is contributed by ik_9 |
Python3
# Python code for the above approach:# Function to find Ndef find_n(x, y): # Mathematical equation from approach N = (x * y) - x + y # Return N return N# Driver Codex = 18y = 42# Function callprint(find_n(x, y))# This Code is Contributed by Prasad Kandekar(prasad264) |
C#
// C# code for the above approachusing System;public class GFG { // Function to find N static int FindN(int x, int y) { // Mathematical equation from approach int N = (x * y) - x + y; // Return N return N; } static public void Main() { // Code int X = 18, Y = 42; // Function call Console.WriteLine(FindN(X, Y)); }}// This code is contributed by lokesh. |
Javascript
// JavaScript code for the above approachfunction FindN(x, y) {// Mathematical equation from approachlet N = (x * y) - x + y;// Return Nreturn N;}let X = 18;let Y = 42;// Function callconsole.log(FindN(X, Y));// This code is contributed by anskalyan3. |
780
Time Complexity: O(1)
Auxiliary Space: O(1)
