Given a positive integer N (N ? 2), the task is to count the number of integers X in the range [2, N] such that X can be used to convert N to 1 using the following operation:
- If N is divisible by X, then update N’s value as N / X.
- Else, update N’s value as N – X.
Examples:
Input: N = 6
Output: 3
Explanation:
The following integers can be used to convert N to 1:
X = 2 => N = 6 -> N = 3 -> N = 1
X = 5 => N = 6 -> N = 1
X = 6 => N = 6 -> N = 1Input: N = 48
Output: 4
Naive Approach: The naive approach for this problem is to iterate through all the integers from 2 to N and count the number of integers that can convert N to 1.
Below is the implementation of the above approach:
C++
// C++ program to count the numbers// which can convert N to 1// using the given operation#include <bits/stdc++.h>using namespace std;// Function to count the numbers// which can convert N to 1// using the given operationint countValues(int n){ int answer = 0; // Iterate through all the integers for (int i = 2; i <= n; i++) { int k = n; // Check if N can be converted // to 1 while (k >= i) { if (k % i == 0) k /= i; else k -= i; } // Incrementing the count if it can // be converted if (k == 1) answer++; } return answer;}// Driver codeint main(){ int N = 6; cout << countValues(N); return 0;} |
Java
// Java program to count the numbers// which can convert N to 1// using the given operationimport java.io.*;import java.util.*;class GFG{ // Function to count the numbers// which can convert N to 1// using the given operationstatic int countValues(int n){ int answer = 0; // Iterate through all the integers for (int i = 2; i <= n; i++) { int k = n; // Check if N can be converted // to 1 while (k >= i) { if (k % i == 0) k /= i; else k -= i; } // Incrementing the count if it can // be converted if (k == 1) answer++; } return answer;}// Driver codepublic static void main(String args[]){ int N = 6; System.out.print(countValues(N));}}// This code is contributed by shivanisinghss2110 |
Python3
# Python3 program to count the numbers# which can convert N to 1# using the given operation# Function to count the numbers# which can convert N to 1# using the given operationdef countValues(n): answer = 0 # Iterate through all the integers for i in range(2, n + 1, 1): k = n # Check if N can be converted # to 1 while (k >= i): if (k % i == 0): k //= i else: k -= i # Incrementing the count if it can # be converted if (k == 1): answer += 1 return answer# Driver codeif __name__ == '__main__': N = 6 print(countValues(N))# This code is contributed by Samarth |
C#
// C# program to count the numbers// which can convert N to 1// using the given operationusing System;class GFG{ // Function to count the numbers// which can convert N to 1// using the given operationstatic int countValues(int n){ int answer = 0; // Iterate through all the integers for (int i = 2; i <= n; i++) { int k = n; // Check if N can be converted // to 1 while (k >= i) { if (k % i == 0) k /= i; else k -= i; } // Incrementing the count if it can // be converted if (k == 1) answer++; } return answer;}// Driver codepublic static void Main(){ int N = 6; Console.Write(countValues(N));}}// This code is contributed by Nidhi_biet |
Javascript
<script> // Javascript program to count the numbers // which can convert N to 1 // using the given operation // Function to count the numbers // which can convert N to 1 // using the given operation function countValues(n) { let answer = 0; // Iterate through all the integers for (let i = 2; i <= n; i++) { let k = n; // Check if N can be converted // to 1 while (k >= i) { if (k % i == 0) k /= i; else k -= i; } // Incrementing the count if it can // be converted if (k == 1) answer++; } return answer; } let N = 6; document.write(countValues(N)); </script> |
Output:
3
Time Complexity: O(N), where N is the given number.
Auxiliary Space: O(1)
Efficient Approach: The idea is to observe that if N is not divisible by X initially, then only the subtraction will be carried throughout as after each subtraction N still wouldn’t be divisible by N. Also these operations will stop when N ? X, and the final value of N will be equal to N mod X.
So, for all the numbers from 2 to N, there are only two possible cases :
- No division operation occurs: For all these numbers, the final value will be equal to N mod X. N will become one in the end only if N mod X = 1. Clearly, for X = N – 1, and all divisors of N – 1, N mod X = 1 holds true.
- Division operation occurs more than once: Division operation will only occur for divisors on N. For each divisor of N say d, perform the division till N mod d != 0. If finally N mod d = 1, then this will be included in the answer else not (using the property derived from Case 1).
Below is the implementation of the above approach:
C++
// C++ program to count the numbers// which can convert N to 1// using the given operation#include <bits/stdc++.h>using namespace std;// Function to count the numbers// which can convert N to 1// using the given operationint countValues(int N){ vector<int> div; // Store all the divisors of N for (int i = 2; i * i <= N; i++) { // If i is a divisor if (N % i == 0) { div.push_back(i); // If i is not equal to N / i if (N != i * i) { div.push_back(N / i); } } } int answer = 0; // Iterate through all the divisors of // N - 1 and count them in answer for (int i = 1; i * i <= N - 1; i++) { // Check if N - 1 is a divisor // or not if ((N - 1) % i == 0) { if (i * i == N - 1) answer++; else answer += 2; } } // Iterate through all divisors and check // for N mod d = 1 or (N-1) mod d = 0 for (auto d : div) { int K = N; while (K % d == 0) K /= d; if ((K - 1) % d == 0) answer++; } return answer;}// Driver codeint main(){ int N = 6; cout << countValues(N); return 0;} |
Java
// Java program to count the numbers// which can convert N to 1// using the given operationimport java.util.*;class GFG{// Function to count the numbers// which can convert N to 1// using the given operationstatic int countValues(int N){ Vector<Integer> div = new Vector<>(); // Store all the divisors of N for(int i = 2; i * i <= N; i++) { // If i is a divisor if (N % i == 0) { div.add(i); // If i is not equal to N / i if (N != i * i) { div.add(N / i); } } } int answer = 0; // Iterate through all the divisors of // N - 1 and count them in answer for(int i = 1; i * i <= N - 1; i++) { // Check if N - 1 is a divisor // or not if ((N - 1) % i == 0) { if (i * i == N - 1) answer++; else answer += 2; } } // Iterate through all divisors and check // for N mod d = 1 or (N-1) mod d = 0 for(int d : div) { int K = N; while (K % d == 0) K /= d; if ((K - 1) % d == 0) answer++; } return answer;}// Driver codepublic static void main(String[] args){ int N = 6; System.out.print(countValues(N));}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to count the numbers# which can convert N to 1# using the given operation# Function to count the numbers# which can convert N to 1# using the given operationdef countValues(N): div = [] i = 2 # Store all the divisors of N while ((i * i) <= N): # If i is a divisor if (N % i == 0): div.append(i) # If i is not equal to N / i if (N != i * i): div.append(N // i) i += 1 answer = 0 i = 1 # Iterate through all the divisors of # N - 1 and count them in answer while((i * i) <= N - 1): # Check if N - 1 is a divisor # or not if ((N - 1) % i == 0): if (i * i == N - 1): answer += 1 else: answer += 2 i += 1 # Iterate through all divisors and check # for N mod d = 1 or (N-1) mod d = 0 for d in div: K = N while (K % d == 0): K //= d if ((K - 1) % d == 0): answer += 1 return answer# Driver codeif __name__=="__main__": N = 6 print(countValues(N))# This code is contributed by rutvik_56 |
C#
// C# program to count the numbers// which can convert N to 1// using the given operationusing System;using System.Collections.Generic;class GFG{// Function to count the numbers// which can convert N to 1// using the given operationstatic int countValues(int N){ List<int> div = new List<int>(); // Store all the divisors of N for(int i = 2; i * i <= N; i++) { // If i is a divisor if (N % i == 0) { div.Add(i); // If i is not equal to N / i if (N != i * i) { div.Add(N / i); } } } int answer = 0; // Iterate through all the divisors of // N - 1 and count them in answer for(int i = 1; i * i <= N - 1; i++) { // Check if N - 1 is a divisor // or not if ((N - 1) % i == 0) { if (i * i == N - 1) answer++; else answer += 2; } } // Iterate through all divisors and check // for N mod d = 1 or (N-1) mod d = 0 foreach(int d in div) { int K = N; while (K % d == 0) K /= d; if ((K - 1) % d == 0) answer++; } return answer;}// Driver codepublic static void Main(String[] args){ int N = 6; Console.Write(countValues(N));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program to count the numbers// which can convert N to 1// using the given operation// Function to count the numbers// which can convert N to 1// using the given operationfunction countValues(N){ var div = []; // Store all the divisors of N for (var i = 2; i * i <= N; i++) { // If i is a divisor if (N % i == 0) { div.push(i); // If i is not equal to N / i if (N != i * i) { div.push(N / i); } } } var answer = 0; // Iterate through all the divisors of // N - 1 and count them in answer for (var i = 1; i * i <= N - 1; i++) { // Check if N - 1 is a divisor // or not if ((N - 1) % i == 0) { if (i * i == N - 1) answer++; else answer += 2; } } // Iterate through all divisors and check // for N mod d = 1 or (N-1) mod d = 0 div.forEach(d => { var K = N; while (K % d == 0) K /= d; if ((K - 1) % d == 0) answer++; }); return answer;}// Driver codevar N = 6;document.write( countValues(N));</script> |
Output:
3
Time Complexity:
Auxiliary Space: O(sqrt(N))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
