# Count divisors which generates same Quotient and Remainder

Given a positive integer **N**, the task is to find the count of all the numbers **M** such that when the number **N** is divided by **M**, the quotient is equal to its remainder i.e **(âŒŠN/MâŒ‹ = N mod M) **where **âŒŠ âŒ‹ **denotes the floor value of a given number.

**Examples:**

Input:N = 8Output:2Explanation:When 8 is divided by 3 and 7, it returns the same Quotient and Remainder.

8 / 3 = 8 % 3, 8 / 7 = 8 % 7. Therefore, the required answer is 2.

Input:N = 1000000000000Output:84

**Naive Approach: **The simplest approach is based on the fact that **M** can not be greater than **N** as for any number greater than **N**, the quotient would be zero. Whereas, its modulo with **N** will always be **N**. Therefore, iterate through all the numbers from **1 to N** and count all such numbers satisfying the given condition.

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

**Efficient Approach: **The optimal idea is based on the observation stated below:

If

(âŒŠN/MâŒ‹ = N mod M), thenM + 1must be a divisor ofN.

**Proof for the observation:**

If

âŒŠN/MâŒ‹ = N mod M, then letN / Mbe equal toK.

Therefore,Nmust be equal toK * M + KasKis the quotient as well as the remainder.

N = K * M + K

N = K * (M + 1)

Therefore, forMto be in our answer set, it is necessary thatM + 1is a divisor ofN.

Note thatM + 1must be a divisor ofNis a necessary condition but not a sufficient condition forâŒŠN/MâŒ‹ = N mod M.

Follow the below steps to solve the problem:

- Find all divisors of N and store them in an array. This can be computed in O(âˆš N) complexity.
- Check for all divisors by iterating through the array, and if divisor minus 1 satisfy the given condition
**âŒŠN / MâŒ‹ = N mod M**, increase the count.

Below is the implementation of the above approach:

## C++

`// C++ program of the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to calculate the` `// count of numbers such that it` `// gives same quotient and remainder` `void` `countDivisors(` `long` `long` `int` `n)` `{` ` ` `int` `count = 0;` ` ` `// Stores divisor of number N.` ` ` `vector<` `long` `long` `int` `> divisor;` ` ` `// Iterate through numbers from 2` ` ` `// to sqrt(N) and store divisors of N` ` ` `for` `(` `int` `i = 2; i <= ` `sqrt` `(n); i++) {` ` ` `if` `(n % i == 0) {` ` ` `if` `(n / i == i)` ` ` `divisor.push_back(i);` ` ` `else` `{` ` ` `divisor.push_back(i);` ` ` `divisor.push_back(n / i);` ` ` `}` ` ` `}` ` ` `}` ` ` `// As N is also divisor of itself` ` ` `divisor.push_back(n);` ` ` `// Iterate through divisors` ` ` `for` `(` `auto` `x : divisor) {` ` ` `x -= 1;` ` ` `// Checking whether x satisfies the` ` ` `// required condition` ` ` `if` `((n / x) == (n % x))` ` ` `count++;` ` ` `}` ` ` `// Print the count` ` ` `cout << count;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given N` ` ` `long` `long` `int` `N = 1000000000000;` ` ` `// Function Call` ` ` `countDivisors(N);` ` ` `return` `0;` `}` |

## Java

`// Java program of the above approach` `class` `GFG {` ` ` ` ` `// Function to calculate the` ` ` `// count of numbers such that it` ` ` `// gives same quotient and remainder` ` ` `static` `void` `countDivisors(` `int` `n)` ` ` `{ ` ` ` `int` `count = ` `0` `;` ` ` `int` `j = ` `0` `;` ` ` ` ` `// Stores divisor of number N.` ` ` `int` `divisor[] = ` `new` `int` `[n];` ` ` ` ` `// Iterate through numbers from 2` ` ` `// to sqrt(N) and store divisors of N` ` ` `for` `(` `int` `i = ` `2` `; i <= Math.sqrt(n); i++) { ` ` ` `if` `(n % i == ` `0` `) {` ` ` `if` `(n / i == i){` ` ` `divisor[j] = i;` ` ` `j += ` `1` `;` ` ` `}` ` ` `else` `{` ` ` `divisor[j] = i;` ` ` `divisor[j + ` `1` `] = n / i; ` ` ` `j += ` `2` `;` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// As N is also divisor of itself` ` ` `divisor[j] = n;` ` ` ` ` `// Iterate through divisors` ` ` `for` `(` `int` `i = ` `0` `; i <= j; i++)` ` ` `{` ` ` `int` `x = divisor[i];` ` ` `x -= ` `1` `;` ` ` ` ` `// Checking whether x satisfies the` ` ` `// required condition` ` ` `if` `((n / x) == (n % x))` ` ` `count++;` ` ` `}` ` ` ` ` `// Print the count` ` ` `System.out.print(count);` ` ` `}` ` ` ` ` `// Driver Code` ` ` `public` `static` `void` `main (String[] args)` ` ` `{` ` ` ` ` `// Given N` ` ` `int` `N = ` `10000000` `;` ` ` ` ` `// Function Call` ` ` `countDivisors(N);` ` ` `}` `}` `// This code is contributed by AnkThon` |

## Python3

`# Python3 program of the above approach` `from` `math ` `import` `floor, sqrt` `# Function to calculate the` `# count of numbers such that it` `# gives same quotient and remainder` `def` `countDivisors(n):` ` ` ` ` `count ` `=` `0` ` ` `# Stores divisor of number N.` ` ` `divisor ` `=` `[]` ` ` `# Iterate through numbers from 2` ` ` `# to sqrt(N) and store divisors of N` ` ` `for` `i ` `in` `range` `(` `2` `, floor(sqrt(n))):` ` ` `if` `(n ` `%` `i ` `=` `=` `0` `):` ` ` `if` `(n ` `/` `/` `i ` `=` `=` `i):` ` ` `divisor.append(i)` ` ` `else` `:` ` ` `divisor.append(i)` ` ` `divisor.append(n ` `/` `/` `i)` ` ` `# As N is also divisor of itself` ` ` `divisor.append(n)` ` ` `# Iterate through divisors` ` ` `for` `x ` `in` `divisor:` ` ` `x ` `-` `=` `1` ` ` `# Checking whether x satisfies the` ` ` `# required condition` ` ` `if` `((n ` `/` `/` `x) ` `=` `=` `(n ` `%` `x)):` ` ` `count ` `+` `=` `1` ` ` `# Print the count` ` ` `print` `(count)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `# Given N` ` ` `N ` `=` `1000000000000` ` ` `# Function Call` ` ` `countDivisors(N)` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program of the above approach` `using` `System;` `class` `GFG {` ` ` ` ` `// Function to calculate the` ` ` `// count of numbers such that it` ` ` `// gives same quotient and remainder` ` ` `static` `void` `countDivisors(` `int` `n)` ` ` `{ ` ` ` `int` `count = 0;` ` ` `int` `j = 0;` ` ` ` ` `// Stores divisor of number N.` ` ` `int` `[]divisor = ` `new` `int` `[n];` ` ` ` ` `// Iterate through numbers from 2` ` ` `// to sqrt(N) and store divisors of N` ` ` `for` `(` `int` `i = 2; i <= Math.Sqrt(n); i++) { ` ` ` `if` `(n % i == 0) {` ` ` `if` `(n / i == i){` ` ` `divisor[j] = i;` ` ` `j += 1;` ` ` `}` ` ` `else` `{` ` ` `divisor[j] = i;` ` ` `divisor[j + 1] = n / i; ` ` ` `j += 2;` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// As N is also divisor of itself` ` ` `divisor[j] = n;` ` ` ` ` `// Iterate through divisors` ` ` `for` `(` `int` `i = 0; i <= j; i++)` ` ` `{` ` ` `int` `x = divisor[i];` ` ` `x -= 1;` ` ` ` ` `// Checking whether x satisfies the` ` ` `// required condition` ` ` `if` `((n / x) == (n % x))` ` ` `count++;` ` ` `}` ` ` ` ` `// Print the count` ` ` `Console.Write(count);` ` ` `}` ` ` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` ` ` `// Given N` ` ` `int` `N = 10000000;` ` ` ` ` `// Function Call` ` ` `countDivisors(N);` ` ` `}` `}` `// This code contributed by shikhasingrajput` |

## Javascript

`<script>` `// Javascript program of the above approach ` `// Function to calculate the` ` ` `// count of numbers such that it` ` ` `// gives same quotient and remainder` ` ` `function` `countDivisors(n)` ` ` `{` ` ` `var` `count = 0;` ` ` `var` `j = 0;` ` ` `// Stores divisor of number N.` ` ` `var` `divisor = Array(n).fill(0);` ` ` `// Iterate through numbers from 2` ` ` `// to sqrt(N) and store divisors of N` ` ` `for` `(` `var` `i = 2; i <= Math.sqrt(n); i++)` ` ` `{` ` ` `if` `(n % i == 0) {` ` ` `if` `(parseInt(n / i) == i)` ` ` `{` ` ` `divisor[j] = i;` ` ` `j += 1;` ` ` `} ` `else` `{` ` ` `divisor[j] = i;` ` ` `divisor[j + 1] = parseInt(n / i);` ` ` `j += 2;` ` ` `}` ` ` `}` ` ` `}` ` ` `// As N is also divisor of itself` ` ` `divisor[j] = n;` ` ` `// Iterate through divisors` ` ` `for` `(` `var` `i = 0; i <= j; i++) {` ` ` `var` `x = divisor[i];` ` ` `x -= 1;` ` ` `// Checking whether x satisfies the` ` ` `// required condition` ` ` `if` `(parseInt(n / x) == parseInt(n % x))` ` ` `count++;` ` ` `}` ` ` `// Print the count` ` ` `document.write(count);` ` ` `}` ` ` `// Driver Code` ` ` ` ` `// Given N` ` ` `var` `N = 10000000;` ` ` `// Function Call` ` ` `countDivisors(N);` `// This code contributed by aashish1995` `</script>` |

**Output:**

84

**Time Complexity:** O(sqrt(N))**Auxiliary Space:** O(sqrt(N))

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**