Dado un número entero N y dos números enteros D1 y D2 ( < 10 ), la tarea es encontrar el número de pares coprimos menores o iguales a N que consisten solo en los dígitos D1 y D2 .
Ejemplos:
Entrada: N = 30, D1 = 2, D2 = 3
Salida: 5
Explicación:
Todos los pares posibles de números hasta 30 que tienen dígitos 2 y 3 que son primos entre sí son (2, 3), (2, 23) , (3, 22), (3, 23), (22, 23) .Entrada: N = 100, D1 = 5, D2 = 6
Salida: 8
Explicación:
Todos los pares posibles de números hasta 100 que tienen dígitos 5 y 6 que son primos entre sí son (5, 6), (5, 56) , (5, 66), (6, 55), (6, 65), (55, 56), (56, 65), (65, 66).
Planteamiento: La idea para resolver este problema se basa en las siguientes observaciones:
Observación:
- Encuentre y agregue cada número que consiste solo en dos dígitos que son menores o iguales a N en una lista.
- Ahora es fácil encontrar el número de pares desordenados que son coprimos.
- Tenga en cuenta que puede haber un máximo de 1 + 2 + 2 2 + 2 3 + 2 4 + ………2 10 = 2047 números en la lista, es decir, la complejidad de tiempo general no puede exceder O (2047 * 2047), ya que el número máximo. de dígitos posibles es 9.
Siga los pasos a continuación para resolver el problema:
- Inicialice una lista vacía , diga l , y agregue los dos dígitos dados como una string en la lista.
- Ordenar la lista .
- Inicialice dos listas, digamos total y temp2 para su uso posterior.
- Iterar hasta l[0] < 10:
- Agregue los dos dígitos dados como una string a todos los elementos presentes en la lista l.
- Continúe actualizando l de la manera que se muestra a continuación:
- [2, 3] -> [‘2’ + ‘2’, ‘2’ + ‘3’, ‘3’ + ‘2’, ‘3’ + ‘3’]
- [22, 23, 32, 33] – > [’22’ + ‘2’, ’22’ + ‘3’, ’23’ + ‘2’, ’23’ + ‘3’, ’32’ + ‘2 ‘, ’32’ + ‘3’, ’33’ + ‘2’, ’33’ + ‘3’] y así sucesivamente.
- Defina una función numOfPairs() que devuelva el recuento de pares coprimos no ordenados.
- Imprime el conteo devuelto por la función anterior como la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether given
// integers are co-prime or not
int coprime(int a, int b) { return (__gcd(a, b) == 1); }
// Utility function to count
// number of co-prime pairs
int numOfPairs(vector<string> arr, int N)
{
int count = 0;
// Traverse the array
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
// If co-prime
if (coprime(stoi(arr[i]), stoi(arr[j]))) {
// Increment count
count = count + 1;
}
}
}
// Return count
return count;
}
// Function to count number
// of co-prime pairs
int noOfCoPrimePairs(int N, int d1, int d2)
{
// Stores digits in string form
vector<string> l;
l.push_back(to_string(d1));
l.push_back(to_string(d2));
// Sort the list
sort(l.begin(), l.end());
if (N < stoi(l[1]))
return 0;
// Keep two copies of list l
vector<string> total = l;
vector<string> temp2 = l;
int flag = 0;
vector<string> temp3;
// Generate 2 digit numbers
// using d1 and d2
while (l[0].length() < 10) {
for (int i = 0; i < l.size(); i++) {
for (int j = 0; j < 2; j++) {
// If current number
// does not exceed N
if (stoi(l[i] + temp2[j]) > N) {
flag = 1;
break;
}
total.push_back(l[i] + temp2[j]);
temp3.push_back(l[i] + temp2[j]);
}
if (flag == 1)
break;
}
if (flag == 1)
break;
l = temp3;
vector<string> temp3;
}
// Stores length of list
int lenOfTotal = total.size();
// Stores number of co-prime pairs
int ans = numOfPairs(total, lenOfTotal);
// Print number of co-prime pairs
cout << (ans);
}
// Driver Code
int main()
{
// Given value of N, d1, d2
int N = 30, d1 = 2, d2 = 3;
// Function call to count
// number of co-prime pairs
noOfCoPrimePairs(N, d1, d2);
}
// This code is contributed by ukasp.
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int GCD(int a, int b)
{
return b == 0 ? a : GCD(b, a % b);
}
// Function to check whether given
// integers are co-prime or not
static boolean coprime(int a, int b)
{
if (GCD(a, b) == 1)
return true;
return false;
}
// Utility function to count
// number of co-prime pairs
static int numOfPairs(ArrayList<String> arr, int N)
{
int count = 0;
// Traverse the array
for(int i = 0; i < N - 1; i++)
{
for(int j = i + 1; j < N; j++)
{
// If co-prime
if (coprime(Integer.parseInt(arr.get(i)),
Integer.parseInt(arr.get(j))))
{
// Increment count
count = count + 1;
}
}
}
// Return count
return count;
}
// Function to count number
// of co-prime pairs
static void noOfCoPrimePairs(int N, int d1, int d2)
{
// Stores digits in string form
ArrayList<String> l = new ArrayList<String>();
l.add(Integer.toString(d1));
l.add(Integer.toString(d2));
// Sort the list
Collections.sort(l);
if (N < Integer.parseInt(l.get(1)))
return;
// Keep two copies of list l
ArrayList<String> total = new ArrayList<String>(l);
ArrayList<String> temp2 = new ArrayList<String>(l);
int flag = 0;
ArrayList<String> temp3 = new ArrayList<String>(l);
// Generate 2 digit numbers
// using d1 and d2
while (l.get(0).length() < 10)
{
for(int i = 0; i < l.size(); i++)
{
for(int j = 0; j < 2; j++)
{
// If current number
// does not exceed N
if (Integer.parseInt(l.get(i) +
temp2.get(j)) > N)
{
flag = 1;
break;
}
total.add(l.get(i) + temp2.get(j));
temp3.add(l.get(i) + temp2.get(j));
}
if (flag == 1)
break;
}
if (flag == 1)
break;
l = temp3;
temp3.clear();
}
// Stores length of list
int lenOfTotal = total.size();
// Stores number of co-prime pairs
int ans = numOfPairs(total, lenOfTotal);
// Print number of co-prime pairs
System.out.print(ans);
}
// Driver Code
public static void main(String args[])
{
// Given value of N, d1, d2
int N = 30, d1 = 2, d2 = 3;
// Function call to count
// number of co-prime pairs
noOfCoPrimePairs(N, d1, d2);
}
}
// This code is contributed by bgangwar59
Python3
# Python3 program for the above approach from copy import deepcopy import math # Function to check whether given # integers are co-prime or not def coprime(a, b): return (math.gcd(a, b)) == 1 # Utility function to count # number of co-prime pairs def numOfPairs(arr, N): count = 0 # Traverse the array for i in range(0, N-1): for j in range(i+1, N): # If co-prime if (coprime(int(arr[i]), int(arr[j]))): # Increment count count = count + 1 # Return count return count # Function to count number # of co-prime pairs def noOfCoPrimePairs(N, d1, d2): # Stores digits in string form l = [] l.append(str(d1)) l.append(str(d2)) # Sort the list l.sort() if int(N) < int(l[1]): return 0 # Keep two copies of list l total = temp2 = deepcopy(l) flag = 0 temp3 = [] # Generate 2 digit numbers # using d1 and d2 while len(l[0]) < 10: for i in range(len(l)): for j in range(2): # If current number # does not exceed N if int(l[i]+temp2[j]) > int(N): flag = 1 break total.append(l[i]+temp2[j]) temp3.append(l[i]+temp2[j]) if flag == 1: break if flag == 1: break l = deepcopy(temp3) temp3 = [] # Stores length of list lenOfTotal = len(total) # Stores number of co-prime pairs ans = numOfPairs(total, lenOfTotal) # Print number of co-prime pairs print(ans) # Driver Code if __name__ == "__main__": # Given value of N, d1, d2 N = 30 d1 = 2 d2 = 3 # Function call to count # number of co-prime pairs noOfCoPrimePairs(N, d1, d2)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int GCD(int a, int b)
{
return b == 0 ? a : GCD(b, a % b);
}
// Function to check whether given
// integers are co-prime or not
static bool coprime(int a, int b)
{
if (GCD(a, b) == 1)
return true;
return false;
}
// Utility function to count
// number of co-prime pairs
static int numOfPairs(List<string> arr, int N)
{
int count = 0;
// Traverse the array
for(int i = 0; i < N - 1; i++)
{
for(int j = i + 1; j < N; j++)
{
// If co-prime
if (coprime(Int32.Parse(arr[i]),
Int32.Parse(arr[j])))
{
// Increment count
count = count + 1;
}
}
}
// Return count
return count;
}
// Function to count number
// of co-prime pairs
static void noOfCoPrimePairs(int N, int d1, int d2)
{
// Stores digits in string form
List<string> l = new List<string>();
l.Add(d1.ToString());
l.Add(d2.ToString());
// Sort the list
l.Sort();
if (N < Int32.Parse(l[1]))
return;
// Keep two copies of list l
List<string> total = new List<string>(l);
List<string> temp2 = new List<string>(l);
int flag = 0;
List<string> temp3 = new List<string>();
// Generate 2 digit numbers
// using d1 and d2
while (l[0].Length < 10)
{
for(int i = 0; i < l.Count; i++)
{
for(int j = 0; j < 2; j++)
{
// If current number
// does not exceed N
if (Int32.Parse(l[i] + temp2[j]) > N)
{
flag = 1;
break;
}
total.Add(l[i] + temp2[j]);
temp3.Add(l[i] + temp2[j]);
}
if (flag == 1)
break;
}
if (flag == 1)
break;
l = temp3;
temp3.Clear();
}
// Stores length of list
int lenOfTotal = total.Count;
// Stores number of co-prime pairs
int ans = numOfPairs(total, lenOfTotal);
// Print number of co-prime pairs
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
// Given value of N, d1, d2
int N = 30, d1 = 2, d2 = 3;
// Function call to count
// number of co-prime pairs
noOfCoPrimePairs(N, d1, d2);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// JavaScript program for the above approach
function GCD(a,b)
{
return b == 0 ? a : GCD(b, a % b);
}
// Function to check whether given
// integers are co-prime or not
function coprime(a,b)
{
if (GCD(a, b) == 1)
return true;
return false;
}
// Utility function to count
// number of co-prime pairs
function numOfPairs(arr,N)
{
let count = 0;
// Traverse the array
for(let i = 0; i < N - 1; i++)
{
for(let j = i + 1; j < N; j++)
{
// If co-prime
if (coprime(parseInt(arr[i]),
parseInt(arr[j])))
{
// Increment count
count = count + 1;
}
}
}
// Return count
return count;
}
// Function to count number
// of co-prime pairs
function noOfCoPrimePairs(N,d1,d2)
{
// Stores digits in string form
let l = [];
l.push(d1.toString());
l.push(d2.toString());
// Sort the list
l.sort();
if (N < parseInt(l[1]))
return;
// Keep two copies of list l
let total = [...l];
let temp2 = [...l];
let flag = 0;
let temp3 = [];
// Generate 2 digit numbers
// using d1 and d2
while (l[0].length < 10)
{
for(let i = 0; i < l.length; i++)
{
for(let j = 0; j < 2; j++)
{
// If current number
// does not exceed N
if (parseInt(l[i] +
temp2[j]) > N)
{
flag = 1;
break;
}
total.push(l[i] + temp2[j]);
temp3.push(l[i] + temp2[j]);
}
if (flag == 1)
break;
}
if (flag == 1)
break;
l = [...temp3];
temp3=[];
}
// Stores length of list
let lenOfTotal = total.length;
// Stores number of co-prime pairs
let ans = numOfPairs(total, lenOfTotal);
// Print number of co-prime pairs
document.write(ans);
}
// Driver Code
// Given value of N, d1, d2
let N = 30, d1 = 2, d2 = 3;
// Function call to count
// number of co-prime pairs
noOfCoPrimePairs(N, d1, d2);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
5
Complejidad de Tiempo: O(2 logN )
Espacio Auxiliar: O(2 logN )