Dado un entero positivo N (N ≥ 2) , la tarea es contar el número de enteros X en el rango [2, N] de modo que X pueda usarse para convertir N en 1 usando la siguiente operación:
- Si N es divisible por X , actualice el valor de N como N / X .
- De lo contrario, actualice el valor de N como N – X.
Ejemplos:
Entrada: N = 6
Salida: 3
Explicación:
Los siguientes números enteros pueden usarse para convertir N a 1:
X = 2 => N = 6 -> N = 3 -> N = 1
X = 5 => N = 6 -> norte = 1
X = 6 => norte = 6 -> norte = 1Entrada: N = 48
Salida: 4
Enfoque ingenuo: el enfoque ingenuo para este problema es iterar a través de todos los enteros de 2 a N y contar el número de enteros que pueden convertir N en 1.
A continuación se muestra la implementación del enfoque anterior:
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 operation
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 code
int 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 operation
import java.io.*;
import java.util.*;
class GFG{
// Function to count the numbers
// which can convert N to 1
// using the given operation
static 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 code
public 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 operation def 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 code if __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 operation
using System;
class GFG{
// Function to count the numbers
// which can convert N to 1
// using the given operation
static 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 code
public 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>
Producción:
3
Complejidad de tiempo: O(N) , donde N es el número dado.
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es observar que si N no es divisible por X inicialmente, entonces solo se llevará a cabo la resta ya que después de cada resta N aún no sería divisible por N. Además, estas operaciones se detendrán cuando N ≤ X, y el valor final de N será igual a N mod X .
Entonces, para todos los números del 2 al N, solo hay dos casos posibles:
- No ocurre ninguna operación de división: para todos estos números, el valor final será igual a N mod X. N se convertirá en uno al final solo si N mod X = 1. Claramente, para X = N – 1, y todos los divisores de N – 1, N mod X = 1 es cierto.
- La operación de división ocurre más de una vez: La operación de división solo ocurrirá para divisores en N. Para cada divisor de N, digamos d, realice la división hasta que N mod d != 0. Si finalmente N mod d = 1, entonces esto se incluirá en la respuesta sino no (usando la propiedad derivada del Caso 1).
A continuación se muestra la implementación del enfoque anterior:
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 operation
int 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 code
int 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 operation
import java.util.*;
class GFG{
// Function to count the numbers
// which can convert N to 1
// using the given operation
static 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 code
public 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 operation def 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 code if __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 operation
using System;
using System.Collections.Generic;
class GFG{
// Function to count the numbers
// which can convert N to 1
// using the given operation
static 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 code
public 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 operation
function 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 code
var N = 6;
document.write( countValues(N));
</script>
Producción:
3
Complejidad del tiempo:
Espacio auxiliar: O(sqrt(N))