Find maximum possible moves to achieve a target integer using Squares

By Ann Roberts On Mar 29, 2023

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 * X

count++

}

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:

Java

import java.util.*;

public class GFG {

public static void main(String args[])

{

int N = 5;

System.out.println(MaxMoves(N));

}

static int MaxMoves(int n)

{

long x = 0;

long y = 0;

int count = 0;

while (x <= n) {

x = (long)Math.sqrt(y) + 1;

y = y + x * x;

count++;

}

return count - 1;

}

Time Complexity: O(1)
Auxiliary Space: O(1)