Problem : We have to find the Kth factor for the Number n.

The Question in Leetcode

Approach 1 : Iterating each Number

This is very simple approach where we have to find the nth factor by iterating each and every number from 1 till ((n/2) +1).

Pseudo Code

• Check whether the given Number N and the position of the Factor K are greater than 1.
• We have to have an variable to find how many factors (numberOfFactorsFound) are found; And we have to find the number half of given number and store it in (numberToIterateTil); this variable is optional.
• The next step is iterating from 1 till numberToIterateTil.
• as we keep on iterating; we have to check whether the Given number (numberToFind) when we do modulo with current iterating number (factorNumberToCheck) i.e., numberToFind % factorNumberToCheck ==0; then we have to increment the number of iterators found (the variable is numberOfFactorsFound).
• if the number of iterator is equal to the Kth iterator; then we have to return that number.
• Once we finish the iteartion; we have to increment the number of iterator found by 1. Because each and every number is itself an factor; for example for 7, the factors are 1,7;
• So if the numberOffactor now found is equal to K, then we will have to return the original number itself. For example the 2nd factor of 7 is 7. else -1.

Java Code

public int kthFactor(int numberToFind, int whichK) {

if(whichK>=1 && numberToFind >=whichK){

    int numberToIterateTil = (numberToFind/2)+1;
    int numberOfFactorsFound = 0;

    int factorToReturn = -1;
    for(int factorNumberToCheck = 1; 
          factorNumberToCheck <= numberToIterateTil; factorNumberToCheck++){
          if(numberToFind % factorNumberToCheck ==0){
        ++numberOfFactorsFound;
        } // end of module check

        if(numberOfFactorsFound == whichK){
            return factorNumberToCheck;
        }
    } // end of For loop


    numberOfFactorsFound +=1;
    return numberOfFactorsFound == whichK ? numberToFind : -1;

    }
return -1;
}

Note: This is not the most optimized solution. As we are iterating till N/2 times and then we need an extra space for the variable (numberOfFactorsFound).

Approach 2 : Itearting and saving numbers

In this approach, we have to find the factor of number and at same time, we will store the reverse factor also.

In previous approach say if we are going to find the 5th factor of 100, we will do itearting from 1, 2,4,5,10,20,25,50,100 then we will have to increment one by one and stop at 20. There are chances the iteration are bit higher in previous code.

In this approach, if the number a1 is factor, then NumbertoFind /a1 is also factor and store. Say for 100, 2 is factor; and also 100/2 =50 is also factor; we will find both 2,50 at same time.

Here we will use two Vectors to save the numbers.

Pseudo Code

• Here we will need two vectors; 1) to store from 1 to Sqrt(n) we will name it as firstHalfDivisor ; the values will be in ascending order and 2) to store from n to sqrt(n); lets call it secondHalfDivisor the values will be in descending order.
• Next we will be iterating from 1 to Sqrt(n) and will be finding the values and populating them.
• if the number say n1 is divising the Number n, then it is stored in the firstHalfDivisor and again the n/n1 is stored in the secondHalfDivisor.
• After we find all factors. we have to move to next stage.
• if the K is greater than size of both vectors; then we return -1. Because it wont exist.
• if K is less than or equal the size of firstHalfDivisor vector, then it will be at the position K-1.
• If the K is greater than size of firstHalfDivisor vector, then it will be in secondHalfDivisor. Since it is in reverse order we have to search from bottom.
• The position in the secondHalfDivisor will be as follows.

First we know the K is the position we want. Its not available in firstHalfDivisor vector. So we have to Subtract firstHalfDivisor size from K; so it is K-firstHalfDivisor.size(); lets call this value has halfK;

Next we have to subtract from size of secondHalfDivisor from halfK; i.e., secondHalfDivisor.size() - halfK; this will be position of the Kth factor.

Instead of this, we can do the sorting of vector; which may be unnecessary iterating of elements.

Java Code

public int kthFactor(int numberToFind, int whichK) {

if(whichK>=1 && numberToFind >=whichK){

    Vector<Integer> firstHalfDivisor = new Vector<Integer>();
    Vector<Integer> secondHalfDivisor = new Vector<Integer>();

    for(int factorNumberToCheck = 1; factorNumberToCheck <= Math.sqrt(numberToFind); factorNumberToCheck++){
        if(numberToFind % factorNumberToCheck ==0){
            firstHalfDivisor.add(factorNumberToCheck);

            if(factorNumberToCheck != Math.sqrt(numberToFind)){
                    secondHalfDivisor.add(numberToFind/factorNumberToCheck);
            }
        }

    }


    if(whichK > (firstHalfDivisor.size() + secondHalfDivisor.size())){
        return -1;
    }else{

        if(whichK<=firstHalfDivisor.size()){
            return firstHalfDivisor.get(whichK-1);
        }else{
            return secondHalfDivisor.get(
secondHalfDivisor.size()- 
(whichK-firstHalfDivisor.size())
);

              }    
    }    

    }
return -1;
}