Find the Factor

Determine the factors of a number (i.e., all positive integer values that evenly divide into a
number) and then return the pth element of the list, sorted ascending. If there is no pth element,
return 0.

Example

n = 20
p=3

The factors of 20 in ascending order are {1, 2, 4, 5, 10, 20}. Using 1-based indexing, if p = 3, then
4 is returned. If p > 6, 0 would be returned.

Function Description

Complete the function pthFactor in the editor below.

pthFactor has the following parameter(s):

int n: the integer whose factors are to be found
int p: the index of the factor to be returned

Returns:
int: the long integer value of the pth integer factor of n or, if there is no factor at that
index, then 0 is returned

Constraints

1 ≤ n ≤ 1015
1 ≤ p ≤ 109

Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function.

The first line contains an integer n, the number to factor.

The second line contains an integer p, the 1-based index of the factor to return.

Sample Case 0
Sample Input 0

STDIN Function
----- --------
10 → n = 10
3 → p = 3

Sample Output 0

5
Explanation 0

Factoring n = 10 results in {1, 2, 5, 10}. Return the p = 3rd factor, 5, as the answer.

Sample Case 1
Sample Input 1

STDIN Function
----- --------
10 → n = 10
5 → p = 5

Sample Output 1

Explanation 1

Factoring n = 10 results in {1, 2, 5, 10}. There are only 4 factors and p = 5, therefore 0 is returned
as the answer.

Sample Case 2
Sample Input 2

STDIN Function
----- --------
1 → n = 1
1 → p = 1

Sample Output 2

Explanation 2

Factoring n = 1 results in {1}. The p = 1st factor of 1 is returned as the answer.

2 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

/*
* Complete the 'pthFactor' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. LONG_INTEGER n
* 2. LONG_INTEGER p
*/

long pthFactor(long n, long p)

{
long i, j, t, count = 0, arr[100000] = { 0 };
for (i = 1; i <= sqrt(n); i++)
{
if (n % i == 0)
{
arr[count++] = i;
if (n / i != i)
arr[count++] = n / i;
}
}
if (count < p)
return 0;
for (i = 0; i < count - 1; i++)
{
for (j = i + 1; j < count - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
return arr[p - 1];
}

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 3

/*
* Complete the 'pthFactor' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. LONG_INTEGER n
* 2. LONG_INTEGER p
*/

long pthFactor(long n, long p)

{
long i, count = 0, arr[100000] = { 0 };
for (i = 1; i <= n; i++) {
if (n % i == 0)
{
arr[count++] = i;
if (count == p)
break;
}
}
if (count < p)
return 0;
return arr[--count];
}

4 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

4
4

1234
2

111111
1

67280421310721
2

67280421310721

866421317361600
26881

866421317361600
26880

866421317361600

100000000000000
200

160000000000

99980000016
56

438508772

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 5

 Prime or Not?

Given an integer, if the number is prime, return 1. Otherwise return its smallest divisor greater
than 1.

Example

n = 24

The number 24 is not prime: its divisors are [1, 2, 3, 4, 6, 8, 12, 24]. The smallest divisor greater
than 1 is 2.

Function Description

Complete the function isPrime in the editor below.

isPrime has the following parameter(s):

long n: a long integer to test

Returns
int: if the number is prime, return 1; otherwise returns the smallest divisor greater than
1

Constraints

2 ≤ n ≤ 1012

Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function.

The only line of input contains the long integer to analyze, n.

Sample Case 0

Sample Input 0

STDIN Function
----- --------
2 → n = 2

Sample Output 0

Explanation 0

As 2 is a prime number, the function returns 1.

6 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

Sample Case 1

Sample Input 1

STDIN Function
----- --------
4 → n = 4

Sample Output 1

Explanation 1

Since 4 is not a prime number, and the factors of 4 are [1, 2, 4], the function returns the smallest
factor of 4 greater than 1.

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 7

/*
* Complete the 'isPrime' function below.
*
* The function is expected to return an INTEGER.
* The function accepts LONG_INTEGER n as parameter.
*/

int isPrime(long n)
{
long i;
for (i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return i;
return 1;
}

8 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

/*
* Complete the 'isPrime' function below.
*
* The function is expected to return an INTEGER.
* The function accepts LONG_INTEGER n as parameter.
*/

int isPrime(long n)
{
long i;
for (i = 2; i <= n / 2; i++)
if (n % i == 0)
return i;
return 1;
}

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 9

13

15

1591827647

28081

1206516341

33029

135583507859

146093

14120520373

112691

108485931109

196159

547790008457

697819

10924515817

103043

10 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

 4th Bit

A binary number is a combination of 1s and 0s. Its nth least significant digit is the nth digit
starting from the right starting with 1. Given a decimal number, convert it to binary and
determine the value of the the 4th least significant digit.

Example

number = 23

 Convert the decimal number 23 to binary number: 2310 = 24 + 22 + 21 + 20 = (10111)2.

 The value of the 4th index from the right in the binary representation is 0.

Function Description

Complete the function fourthBit in the editor below.

fourthBit has the following parameter(s):

int number: a decimal integer

Returns:
int: an integer 0 or 1 matching the 4th least significant digit in the binary representation
of number.

Constraints

0 ≤ number < 231

Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function.

The only line contains an integer, number.

Sample Case 0

Sample Input 0

STDIN Function
----- --------
32 → number = 32

Sample Output 0

Explanation 0

 Convert the decimal number 32 to binary number: 3210 = (100000)2.

 The value of the 4th index from the right in the binary representation is 0.

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 11

Sample Case 1

Sample Input 1

STDIN Function
----- --------
77 → number = 77

Sample Output 1

Explanation 1

 Convert the decimal number 77 to binary number: 7710 = (1001101)2.

 The value of the 4th index from the right in the binary representation is 1.

12 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

/*
* Complete the 'fourthBit' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER number as parameter.
*/

int fourthBit(int number)

{
int bit;
bit = (number >> 3) & 1;
return bit;
}

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 13

90998

360001

9077971

9077071

2147483647

14 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

 Additional

PowerSum

Given two integers, l and r, find the number of integers x such that l ≤ x ≤ r, and x is a Power
Number.

A Power Number is defined as an integer that can be represented as sum of two powers, i.e.

x = ap + bq
a, b, p and q are all integers
a, b ≥ 0
p, q > 1

For example, given l=20 and r=25:

20 = 22 + 42
24 = 23 + 42
25 = 32 + 42

Function Description

Complete the function countPowerNumbers in the editor below. The function must return the
integer count of power numbers in the given range.

countPowerNumbers has the following parameter(s):

l: integer, the lower limit of the inclusive range
r: integer, the upper limit of the inclusive range

Constraints:

0 ≤ l ≤ r ≤ 5 ×106

Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function.

The first line contains an integer l.

The next line contains an integer r.

Sample Case 0

Sample Input 0

0
1

Sample Output 0

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 15

Explanation 0

0 and 1 both are Power Numbers.

0 = 02 + 02
1 = 02 + 12

Sample Case 1

Sample Input 1

25
30

Sample Output 1

Explanation 1

Except 30, all are Power Numbers.

25 = 52 + 02
26 = 52 + 12
27 = 33 + 02
28 = 33 + 12
29 = 52 + 22

16 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College

/*
* Complete the 'countPowerNumbers' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER l
* 2. INTEGER r
*/

[Link] | AP (SG) | CSE | Rajalakshmi Engineering College 17

103
103

1
100

60

1
27

17

0
41

29

500
1300

350

27
467

246

2
499999

149068

1
1000000

284029

18 [Link] | AP (SG) | CSE | Rajalakshmi Engineering College