Given an integer X, and A, B having value initially 0, the task is to find the maximum number of possible moves we can make to make A equal to X such that in each move we can choose any positive number whose square is greater than the current value of B and update A to that particular number chosen and add the square of the number to B.
Examples:
Input: X = 5
Output: 4
Explanation: The possible sequence of values of X can be: 0 -> 1 -> 2 -> 3 -> 5, Which takes 4 moves. The moves are as follows:
- A = 0, B = 0
- First Move: Let take positive integer 1, because 1*1 is greater than current value of B (B = 0). So, update A as 1 and B = 0 + (1*1) = 1.
- X = 1, Y = 1
- Second Move: Let take positive integer 2, because 2*2 is greater than current value of B (B = 1). So, update A as 2 and B = 1 + (2*2) = 5.
- X = 2, Y = 5
- Third Move: Let take positive integer 3, because 3*3 is greater than current value of B (B = 5). So, update A as 3 and B = 5 + (3*3) = 14.
- X = 3, Y = 14
- Fourth Move: Let take positive integer 5, because 5*5 is greater than current value of B (B = 14). So, update A as 5 and B = 14 + (5*5) = 39.
- X = 5, Y = 39
Now, We have reached at A = 5, It can be verified that following the given rule of the game, 4 is the maximum number of possible moves we can make from reaching A = 0 to A = 5.
Input: X = 8
Output: 5
Explanation: The possible sequence of values of X can be: 0 -> 1 -> 2 -> 3 -> 5 -> 8, Which takes 5 moves. It can be verified that there is no possible number of moves greater than 5, such that following the above-defined rule, We can reach from X = 0 to X = 8.
Approach: Implement the idea below to solve the problem:
The problem is based on mathematical logic. The idea of the problem is defined as below in the Concept of approach section.
Concept of Approach:
The problem is mathematical logic based and can be solved by using some mathematical observations. The algorithm and observation for solving the problem is defined below for the input value of X in variable N.
Take variables A, B, count = 0
// Observation
while (A ≤ X){
A = Math.sqrt(B) + 1
B = B + X * Xcount++
}
The maximum number of moves will be count – 1.
Follow the steps to solve the problem:
- Initialize integers A, B, and Count as 0.
- While (A ≤ X) follow below – mentioned steps under the scope of the while loop:
- A = sqrt( B ) + 1
- B = B + (X * X)
- Count = Count + 1
- Return Count – 1.
Below is the code to implement the approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;int MaxMoves(int n){ // X and Y Variables of game int x = 0; int y = 0; // Count variable for storing // Max number of possible moves int count = 0; // Implementing logic while (x <= n) { x = sqrt(y) + 1; y = y + (x * x); count++; } // Returing maximum moves return count - 1;}int main(){ // Input value of X as variable N // after making certain moves of game int N = 5; // Function call cout << MaxMoves(N);} |
Java
// Java code to implement the approachimport java.util.*;public class GFG { // Driver code public static void main(String args[]) { // Input value of X as variable N // after making certain moves of game int N = 5; // Function call System.out.println(MaxMoves(N)); } static int MaxMoves(int n) { // X and Y Variables of game long x = 0; long y = 0; // Count variable for storing // Max number of possible moves int count = 0; // Implementing logic while (x <= n) { x = (long)Math.sqrt(y) + 1; y = y + x * x; count++; } // Returing maximum moves return count - 1; }} |
Python3
# Python3 code to implement the approachimport mathdef max_moves(n): # X and Y Variables of game x = 0 y = 0 # Count variable for storing # Max number of possible moves count = 0 # Implementing logic while x <= n: x = int(math.sqrt(y)) + 1 y = y + (x * x) count += 1 # Returning maximum moves return count - 1# Input value of X as variable N# after making certain moves of gamen = 5# Function callprint(max_moves(n)) |
C#
using System;public class Program{ public static int MaxMoves(int n) { // X and Y Variables of game int x = 0; int y = 0; // Count variable for storing // Max number of possible moves int count = 0; // Implementing logic while (x <= n) { x = (int)Math.Sqrt(y) + 1; y = y + (x * x); count++; } // Returing maximum moves return count - 1; } public static void Main() { // Input value of X as variable N // after making certain moves of game int N = 5; // Function call Console.WriteLine(MaxMoves(N)); }} |
Javascript
// JavaScript code to implement the approachfunction MaxMoves(n) {// X and Y Variables of gamelet x = 0;let y = 0;// Count variable for storing// Max number of possible moveslet count = 0;// Implementing logicwhile (x <= n) {x = Math.floor(Math.sqrt(y)) + 1;y = y + (x * x);count++;}// Returning maximum movesreturn count - 1;}// Input value of X as variable N// after making certain moves of gameconst N = 5;// Function callconsole.log(MaxMoves(N)); |
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach: using Binary Search
Concept of Approach:
In this approach, first find the largest sqaure number less than or equal to the current value and update to the
next integer greater than the current value.
Follow the steps to solve the problem:
- Initialize A and B to 0.
- Also, initialize the counter to 0.
- When A < X, do the following:
1. use the binary search and check if (A+mid)^2 is greater than B.
2. If yes, update num and search for a smaller number.
3. If no suitable number is found, break out of the loop.
4. Otherwise, update A and B and increment the move count.
5. Increment the counter. - Last, print the maximum number of moves.
Below is the code to implement the approach:
C++
#include<bits/stdc++.h>using namespace std;int main(){ // Initialize the variables int X=5, A=0, B=0, count=0; while(A<X){ // Initialize the search range for a suitable number int low = 1, high = X-A, mid, num=-1; while(low<=high){ mid = (low+high)/2; if((A+mid)*(A+mid) > B) { num = mid; high = mid-1; } else low = mid+1; } // If no suitable number is found, break out of the loop if(num == -1) break; // Otherwise, update A and B and increment the move count A += num; B += A*A; count++; } cout<<count<<endl; return 0;} |
Java
import java.io.*;public class Geek { public static void main(String[] args) { // Initialize the variables int X = 5, A = 0, B = 0, count = 0; while (A < X) { // Initialize the search range for a suitable number int low = 1, high = X - A, mid, num = -1; while (low <= high) { mid = (low + high) / 2; if ((A + mid) * (A + mid) > B) { // If the condition is satisfied // update num and shrink the search range num = mid; high = mid - 1; } else { // If the condition is not satisfied // expand the search range low = mid + 1; } } // If no suitable number is found // break out of the loop if (num == -1) { break; } A += num; B += A * A; count++; } // Print the final count System.out.println(count); }} |
Python3
# Python code# Initialize the variablesX = 5A = 0B = 0count = 0while A < X: # Initialize the search range for a suitable number low = 1 high = X - A num = -1 # Initialize num here while low <= high: mid = (low + high) // 2 if (A + mid) * (A + mid) > B: num = mid # Update num when a suitable number is found high = mid - 1 else: low = mid + 1 # If no suitable number is found, break out of the loop if num == -1: break else: # Otherwise, update A and B and increment the move count A += num B += A * A count += 1print(count)# This code is contributed by guptapratik |
C#
using System;class Program { static void Main() { // Initialize the variables int X = 5, A = 0, B = 0, count = 0; while (A < X) { // Initialize the search range for a suitable // number int low = 1, high = X - A, mid, num = -1; while (low <= high) { mid = (low + high) / 2; if ((A + mid) * (A + mid) > B) { num = mid; high = mid - 1; } else { low = mid + 1; } } // If no suitable number is found, break out of // the loop if (num == -1) break; // Otherwise, update A and B and increment the // move count A += num; B += A * A; count++; } Console.WriteLine(count); }} |
Javascript
function main() { // Initialize the variables let X = 5, A = 0, B = 0, count = 0; while (A < X) { // Initialize the search range for a suitable number let low = 1, high = X - A, mid, num = -1; while (low <= high) { mid = Math.floor((low + high) / 2); if ((A + mid) * (A + mid) > B) { // If the condition is satisfied // update num and shrink the search range num = mid; high = mid - 1; } else { // If the condition is not satisfied // expand the search range low = mid + 1; } } // If no suitable number is found // break out of the loop if (num === -1) { break; } A += num; B += A * A; count++; } // Print the final count console.log(count);}// Call the main functionmain(); |
4
Time Complexity: O(X*log(X)), where X is the input integer.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
