Skip to content
Home » Programming » Kth largest factor of N in Python and C (TCS CodeVita)

Kth largest factor of N in Python and C (TCS CodeVita)

Kth largest factor of N in C and python with explanation

In this post, we will find the Kth largest factor of N in python and C and explain how we can find it. This problem was asked in TCS CodeVita.

Let’s look at the problem first. After that we will see how we can solve it and explain the process.

Question 

A positive integer d is said to be a factor of another positive integer N if when N is divided by d, the remainder obtained is zero. For example, for number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two factors, 1 and the number k itself. Given two positive integers N and k, write a program to print the kth largest factor of N.

Input Format

The input is a comma-separated list of positive integer pairs (N, k).

Output Format

The kth highest factor of N. If N does not have k factors, the output should be 1.

Constraint

1<N<10000000000
1<k<600.

You can assume that N will have no prime factors which are larger than 13.

Example 1

Input: 12,3
Output: 4

Explanation: N is 12, k is 3. The factors of 12 are (1,2,3,4,6,12). The highest factor is 12 and the third largest factor is 4. The output must be 4.

Example 2

Input: 30,9
Output: 1

Explanation: N is 30, k is 9. The factors of 30 are (1,2,3,5,6,10,15,30). There are only 8 factors. As k is more than the number of factors, the output is 1.

How will we find the Kth largest factor of N?

Here, we have to find the kth largest factor. For this reason, it will be easier for us to start finding the factor from the largest one. So, we will start from the number itself since the number itself is the largest factor of the number. And we will end finding the number when we reach 1 since the smallest factor of every number is 1.

We will increment the value of count every time we find a factor. Then, we will compare count with the kth i.e. position of factor from the largest and if it matches we will print the current factor. If we will not have the number of factors equal to required k then we will print 1 at last.

Algorithm to find the Kth largest factor of N

This algorithm will give you idea about the steps we will be carrying to find out the largest factor of N.

Step 1: Start.
Step 2: Take positive integers as input in N and k.
Step 3: Initialize i = N and repeat steps 5 to 7 until i >= 1,
Step 4: If N % i == 0 increment c by 1
             i.e. count = count + 1
Step 5: If count == k print the value of i and end the loop,
             i.e. printf(“%d”, i);
             break;
Step 6: Decrement i  by 1,
             i.e. i = i - 1
Step 7: If count < k print 1,
             i.e. printf(“1”);
Step 8: End.

In short,

Start,
     Take input in N and k
     i = N, count = 0

     Repeat until i >= 1,
          if N % i == 0,
               count = count + 1
          if count == k,
               print i
               break
          i = i - 1

     if count < k,
          print 1
End.

Program to find the Kth largest factor of N in Python

The program to find the kth largest factor of N in Python programming language is same as the C Programming language only with the difference in their syntax. Lets write a program implemented in Python.

N, k = [int(x) for x in input().split(',')]
count = 0
for i in range(N, 0, -1):
    if((N % i) == 0):
        count += 1
    if(count == k):
        print(i)
        break
        
if count < k:
    print("1")
    

Output

12,3
4
30,9                                                                 
1  

Also Read: Railway Station CodeVita Solution in Python

Explanation

  • To take input, we are using the list comprehension method. Since we have to take comma separated input this method is helpful.
N, k = [int(x) for x in input().split(',')]

With the function input() we are taking input and splitting the input values using split(‘,’) whenever “,” is encountered. And we are doing type conversion of the input to int type. Finally the first value is assigned to variable N and second one to variable k.

  • After that, we will find the kth factor using a for loop.
for i in range(N, 0, -1):
     . . .

Loop runs from N to 1 with decrementing value of -1 in each iteration. We are running the loop from the highest value of factor of a number (i.e. N) to lowest value of factor of a number (i.e. 1).

  • Next, we will check if the current value of i is the factor of N or not.
if((N % i) == 0):
     count += 1

If i is the factor of N we will increment the value of the count by 1. Value of count will help us to determine the kth position of the factor.

  • Straightaway, we will check if the current factor is the required kth factor. This can be done by checking if the count is equals to k.
if(count == k):
     print(i)
     break

If yes, we will print the value of factor i.e. value of i and break the loop since we have already found the kth largest factor.

  • Finally, we will check if the entered value of k is more than the number of factors of N. In that case, we will print “1“.
if count < k:
     print("1")

Program to find the Kth largest factor of N in C

Here we will be implementing the above algorithm to write a program to find the largest factor of N in C programming language.

#include <stdio.h>

int main() {
    int N, k, i, count=0;
    
    // take input 
    scanf("%d,",&N);
    scanf("%d",&k);
    
    // Finding the factor and checking if it is kth largest
    for(i = N; i >= 1; i--) {
        if((N % i) == 0) {
            count++;
        }
        if(count == k) {
            printf("%d", i);
            break;
        }
    }
    
    // check if we found the kth factor
    if(count < k) {
        printf("1");
    }
        
    return 0;
}

Output

12,3
4
30,9
1

Explanation

  • At first, input is taken where N and k are separated using a comma.
scanf("%d,",&N);
scanf("%d",&k);

Please note that the comma along with %d in the first scanf is intentional. Since, we have to separate the input values with the comma this is required.

  • After that, we will run the loop until we find the kth factor.
for(i = N; i >= 1; i--) {
     . . .
}

Here, we initialized i = N and ran the loop until i >= 1.

  • Then, we check the factor using the statement,
if((N % i) == 0) {
     count++;
}

If i is the factor of N we will increment the value of count by 1.

  • Without delay, we will check if the current factor is the kth largest factor or not. If this is the case, we will print the factor and break the loop if the current factor is the kth largest factor.

We will check if the current factor is the kth largest factor of N by,

if(count == k) {
     printf("%d", i);
     break;
}
  • Finally, if k is more than the number of factors of N we will print “1“.
if(count < k) {
     printf("1");
}

Leave a Reply

Your email address will not be published. Required fields are marked *