Find largest factor of N such that NF is less than K in Java

10 Sept 2024 | 4 min read

Given two numbers, N and K, our task is to determine the lowest value X such that N < X*K.

Example 1:

Input:

int num = 8

int K = 7

Output:

The largest factor of N is 2.

Explanation:

For the given number, numbers less than K divisible by N are 1, 2, and 4. So the minimum value of X is 2 such that 8 < 2*7 = 14. Hence, the largest factor of N is 2.

Example 2:

Input:

int num = 999999733,

int K = 999999732

Output:

The largest factor of N is 999999733.

Explanation:

Since the integer 999999733 is a prime number, it can be divided by both 1 and the number itself; because K is smaller than 999999733. Since 999999733 < 999999733*999999732, it can be determined that 999999733 is the minimum value of X. Hence, the largest factor of N is 999999733.

Approach: Na�ve Approach

Equation K * X = N can be used to represent the given problem expression. The primary objective of this equation is to reduce X. Therefore, we must determine the largest K that divides N.

Algorithm:

Step 1: Initialize the variables k and num.

Step 2: Go over [1, K] repeatedly.

Step 3: Declare the temporary variable that will be used to hold the needed response.

Step 4: Verify that (n % i) = 0 for each integer i.

Step 4.1: Continue updating the max variable, which keeps track of the greatest N divisor traversed up to i.

Step 5: Num/maxi, which must be returned, is the required answer.

Implementation:

FileName: LargestFactorofN.java

Output:

The largest factor of N is 2

Complexity Analysis:

The Time Complexity of the above code is O(K), and the Space complexity is O(1).

Approach: Efficient Approach

This approach, which iterates through factors up to the number's square root, effectively determines the largest factor of a given number num that is less than or equal to a set threshold K. It does this by using fundamental mathematical characteristics.

Algorithm:

Step 1: Create a function to determine the largest number factor that stays inside K's value.

Step 2: Create a variable called res to hold the outcome; it should start at 0.

Step 3: Repeats step 1 through step j, up to the square root of num.

Step 4: It determines whether j is a factor of num for each j by determining whether num modulo j equals 0.

Step 5: It compares j with K if j is a factor. It updates res to the maximum of its current value and j if j is less than or equal to K.

Step 6: It also determines whether num divided by j is equal to or less than K. If this is the case, it indicates that num/j is a factor that is either equal to or less than K, in which case res is updated as needed.

Step 7: Finally, the function returns the largest factor (res) that is less than or equal to K.