Given three integers N, X and Y, the task is to check if N can be obtained from 0 using the following operations:
- The current integer can be incremented by one (i.e., x = x + 1) and this can be done at most X times.
- Double the current integer (i.e., x = 2 * x) and this can be done at most Y times.
Return false if the number cannot be reached.
Examples:
Input: N = 24, X = 6 ,Y = 2
Output: true
Explanation: Initially, a = 0
Increment once so a = 1
Increment once so a = 2
Increment once so a = 3
Increment once so a = 4
Increment once so a = 5
Increment once so a = 6
Double once so a = 12
Double again so a = 24Input: N = 4, X = 2 ,Y = 0
Output: false
Approach: The question can also be considered in the exact opposite scenario, where N is given and we need to reduce it to 0 by using two operations :
- Dividing target by 2 as many as maxDoubles times
- Decrementing target by 1 as many as maxadd times.
Use recursive function in this way to check if 0 can be obtained or not. In each recursive scenario decrement 1 and call the function again. And if the number is even divide it by 2 and call the recursive function. If 0 can be obtained for within the given limit of moves return true. Otherwise, return false.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if N is reachedbool checktogetTarget(int N, int X, int Y){ // If N is already zero return true if (N == 0) return true; // If can't double and increment, // just return false if (Y == 0 && X == 0) return false; int temp = N; while (1) { // If N is not divisible by 2, // then just decrement it by 1 if (temp % 2 == 0 && Y != 0) { temp = temp / 2; Y--; } else if (X != 0) { temp--; X--; } if (temp == 0) break; if (Y == 0 && X == 0) break; } // if temp becomes 0 after // performing operation if (temp == 0) { return true; } else { return false; }}// Driver Codeint main(){ int N = 24; int X = 6; int Y = 2; bool ans = checktogetTarget(N, X, Y); if (ans) cout << "true"; else cout << "false"; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to check if N is reached static Boolean checktogetTarget(int N, int X, int Y) { // If N is already zero return true if (N == 0) return true; // If can't double and increment, // just return false if (Y == 0 && X == 0) return false; int temp = N; while (true) { // If N is not divisible by 2, // then just decrement it by 1 if (temp % 2 == 0 && Y != 0) { temp = temp / 2; Y--; } else if (X != 0) { temp--; X--; } if (temp == 0) break; if (Y == 0 && X == 0) break; } // if temp becomes 0 after // performing operation if (temp == 0) { return true; } else { return false; } } // Driver Code public static void main (String[] args) { int N = 24; int X = 6; int Y = 2; Boolean ans = checktogetTarget(N, X, Y); if (ans) System.out.print("true"); else System.out.print("false"); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach # Function to check if N is reacheddef checktogetTarget(N, X, Y): # If N is already zero return true if (N == 0): return True; # If can't double and increment, # just return false if (Y == 0 and X == 0): return False; temp = N; while (1): # If N is not divisible by 2, # then just decrement it by 1 if (temp % 2 == 0 and Y != 0): temp = temp / 2; Y -= 1 elif (X != 0): temp -= 1 X -= 1 if (temp == 0): break; if (Y == 0 and X == 0): break; # if temp becomes 0 after # performing operation if (temp == 0): return True else: return False# Driver CodeN = 24;X = 6;Y = 2;ans = checktogetTarget(N, X, Y);if (ans): print("true");else: print("false");# This code is contributed by Saurabh Jaiswal |
C#
// C# program for above approachusing System;class GFG{ // Function to check if N is reached static bool checktogetTarget(int N, int X, int Y) { // If N is already zero return true if (N == 0) return true; // If can't double and increment, // just return false if (Y == 0 && X == 0) return false; int temp = N; while (true) { // If N is not divisible by 2, // then just decrement it by 1 if (temp % 2 == 0 && Y != 0) { temp = temp / 2; Y--; } else if (X != 0) { temp--; X--; } if (temp == 0) break; if (Y == 0 && X == 0) break; } // if temp becomes 0 after // performing operation if (temp == 0) { return true; } else { return false; } } // Driver Code public static void Main() { int N = 24; int X = 6; int Y = 2; bool ans = checktogetTarget(N, X, Y); if (ans) Console.Write("true"); else Console.Write("false"); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to check if N is reached function checktogetTarget(N, X, Y) { // If N is already zero return true if (N == 0) return true; // If can't double and increment, // just return false if (Y == 0 && X == 0) return false; let temp = N; while (1) { // If N is not divisible by 2, // then just decrement it by 1 if (temp % 2 == 0 && Y != 0) { temp = temp / 2; Y--; } else if (X != 0) { temp--; X--; } if (temp == 0) break; if (Y == 0 && X == 0) break; } // if temp becomes 0 after // performing operation if (temp == 0) { return true; } else { return false; } } // Driver Code let N = 24; let X = 6; let Y = 2; let ans = checktogetTarget(N, X, Y); if (ans) document.write("true"); else document.write("false"); // This code is contributed by Potta Lokesh </script> |
Output
true
Time Complexity: O(N)
Auxiliary Space: O(1)
Share your thoughts in the comments
