Número de pares coprimos obtenidos de la suma de dígitos de elementos en el rango dado

Dados dos números A y B donde 1 <= A <= B. La tarea es contar el número de pares cuyos elementos son coprimos donde los pares se forman a partir de la suma de los dígitos de los elementos en el rango dado. 

Nota: dos pares se cuentan como distintos si al menos uno de los números del par es diferente. Se puede suponer que la suma máxima de dígitos puede ser 162.

Ejemplos:  

Input: 12 15
Output: 4
12 = 1+2 = 3
13 = 1+3 = 4
14 = 1+4 = 5
15 = 1+5 = 6
Thus pairs who are co-prime to each other are 
(3, 4), (3, 5), (4, 5), (5, 6) 
i.e the answer is 4.


Input: 7 10
Output: 6

Método 1:  

  • Considere todos y cada uno de los elementos de a a b.
  • Encuentra la suma de los dígitos de cada elemento y guárdala en un vector.
  • Considere todos y cada uno de los pares uno por uno y verifique si el mcd de los elementos de ese par es 1.
  • En caso afirmativo, cuente ese par ya que es coprimo.
  • Imprime el conteo de pares que son coprimos.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to count the pairs
// whose sum of digits is co-prime
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the elements
// after doing the sum of digits
int makePairs(vector<int> &pairs, int a, int b)
{
     
    // Traverse from a  to b
    for (int i = a; i <= b; i++)
    {
         
    // Find the sum of the digits of the elements
    // in the given range one by one
      int sumOfDigits = 0, k = i;
      while(k>0)
      {
          sumOfDigits += k%10;
          k /= 10;
      }
      if (sumOfDigits <= 162)
      pairs.push_back(sumOfDigits);
    }
}
 
// Function to count the co-prime pairs
int countCoPrime(int a, int b){
    vector<int> pairs;
     
    // Function to make the pairs
    // by doing the sum of digits
    makePairs(pairs, a, b);
    int count = 0;
     
    // Count pairs that are co-primes
    for(int i = 0; i < pairs.size(); i++)
       for (int j = i+1; j < pairs.size(); j++)
          if (__gcd(pairs[i], pairs[j]) == 1)
                 count++;
              
   return count;
     
}
 
// Driver code
int main()
{
    int a = 12, b = 15;
 
    // Function to count the pairs
    cout << countCoPrime(a, b) ;
 
    return 0;
}

Java

// Java program to count the pairs
// whose sum of digits is co-prime
import java.util.*;
 
class GFG
{
static int GCD(int a, int b)
{
if (b == 0) return a;
return GCD(b, a % b);
}
// Function to find the elements
// after doing the sum of digits
static void makePairs(Vector<Integer> pairs,
                      int a, int b)
{
     
    // Traverse from a to b
    for (int i = a; i <= b; i++)
    {
         
    // Find the sum of the digits
    // of the elements in the given
    // range one by one
    int sumOfDigits = 0, k = i;
    while(k > 0)
    {
        sumOfDigits += k % 10;
        k /= 10;
    }
    if (sumOfDigits <= 162)
        pairs.add(sumOfDigits);
    }
}
 
// Function to count
// the co-prime pairs
static int countCoPrime(int a, int b)
{
    Vector<Integer> pairs = new Vector<Integer>();
     
    // Function to make the pairs
    // by doing the sum of digits
    makePairs(pairs, a, b);
    int count = 0;
     
    // Count pairs that are co-primes
    for(int i = 0; i < pairs.size(); i++)
    for (int j = i+1; j < pairs.size(); j++)
        if (GCD(pairs.get(i),
                pairs.get(j)) == 1)
                count++;
             
return count;
     
}
 
// Driver code
public static void main(String args[])
{
    int a = 12, b = 15;
 
    // Function to count the pairs
    System.out.println(countCoPrime(a, b));
}
}
 
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to count the pairs
# whose sum of digits is co-prime
from math import gcd
# Function to find the elements
# after doing the sum of digits
def makePairs(pairs, a, b):
    # Traverse from a to b
    for i in range(a,b+1,1):
        # Find the sum of the digits of the elements
        # in the given range one by one
        sumOfDigits = 0
        k = i
        while(k>0):
            sumOfDigits += k%10
            k = int(k / 10)
     
        if (sumOfDigits <= 162):
            pairs.append(sumOfDigits)
     
# Function to count the co-prime pairs
def countCoPrime(a, b):
    pairs = []
     
    # Function to make the pairs
    # by doing the sum of digits
    makePairs(pairs, a, b)
    count = 0
     
    # Count pairs that are co-primes
    for i in range(0,len(pairs),1):
            for j in range(i+1,len(pairs),1):
                if (gcd(pairs[i], pairs[j]) == 1):
                    count += 1
                     
    return count
     
# Driver code
if __name__ == '__main__':
    a = 12
    b = 15
 
    # Function to count the pairs
    print (countCoPrime(a, b))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to count the pairs
// whose sum of digits is co-prime
using System;
using System.Collections.Generic;
 
class GFG
{
public static int GCD(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    return GCD(b, a % b);
}
 
// Function to find the elements
// after doing the sum of digits
public static void makePairs(List<int> pairs,
                                int a, int b)
{
 
    // Traverse from a to b
    for (int i = a; i <= b; i++)
    {
 
    // Find the sum of the digits
    // of the elements in the given
    // range one by one
    int sumOfDigits = 0, k = i;
    while (k > 0)
    {
        sumOfDigits += k % 10;
        k /= 10;
    }
    if (sumOfDigits <= 162)
    {
        pairs.Add(sumOfDigits);
    }
    }
}
 
// Function to count
// the co-prime pairs
public static int countCoPrime(int a, int b)
{
    List<int> pairs = new List<int>();
 
    // Function to make the pairs
    // by doing the sum of digits
    makePairs(pairs, a, b);
    int count = 0;
 
    // Count pairs that are co-primes
    for (int i = 0;
             i < pairs.Count; i++)
    {
    for (int j = i + 1;
             j < pairs.Count; j++)
    {
        if (GCD(pairs[i], pairs[j]) == 1)
        {
                count++;
        }
    }
    }
 
    return count;
 
}
 
// Driver code
public static void Main(string[] args)
{
    int a = 12, b = 15;
 
    // Function to count the pairs
    Console.WriteLine(countCoPrime(a, b));
}
}
 
// This code is contributed
// by Shrikant13

Javascript

<script>
 
// Javascript program to count the pairs
// whose sum of digits is co-prime
function GCD(a, b)
{
    if (b == 0)
        return a;
         
    return GCD(b, a % b);
}
 
// Function to find the elements
// after doing the sum of digits
function makePairs(pairs, a, b)
{
     
    // Traverse from a to b
    for(i = a; i <= b; i++)
    {
         
        // Find the sum of the digits
        // of the elements in the given
        // range one by one
        var sumOfDigits = 0, k = i;
         
        while (k > 0)
        {
            sumOfDigits += k % 10;
            k = parseInt(k / 10);
        }
        if (sumOfDigits <= 162)
            pairs.push(sumOfDigits);
    }
}
 
// Function to count
// the co-prime pairs
function countCoPrime(a, b)
{
    var pairs = [];
 
    // Function to make the pairs
    // by doing the sum of digits
    makePairs(pairs, a, b);
    var count = 0;
 
    // Count pairs that are co-primes
    for(i = 0; i < pairs.length; i++)
        for(j = i + 1; j < pairs.length; j++)
            if (GCD(pairs[i], pairs[j]) == 1)
                count++;
 
    return count;
 
}
 
// Driver code
var a = 12, b = 15;
 
// Function to count the pairs
document.write(countCoPrime(a, b));
 
// This code is contributed by umadevi9616
 
</script>
Producción: 

4

 

Método 2: 
como se menciona en la pregunta, la suma máxima puede ser 162. Entonces, averigüe la frecuencia de los números que tienen su suma de dígitos de 1 a 162 en el rango A a B y almacene la frecuencia en la array. Luego, encuentra la respuesta usando esta frecuencia. 
Ya que,

Número, Frecuencia 
1, 0 
2, 0 
3, 1 
4, 1 
5, 1 
6, 1 
7, 0 
8, 0 
., . 
., . 
162, 0 
Así Número de pares de mcd = frecuencia(3)*frecuencia(4) + frecuencia(3)*frecuencia(5) + frecuencia(4)*frecuencia(5) + frecuencia(5)* frecuencia(6) 
= 1 +1+1+1 
= 4
 

Por lo tanto, los pares coprimos entre sí son (3,4), (3,5), (4,5), (5,6), es decir, la respuesta es 4. 

A continuación se muestra la implementación requerida:  

C++

// C++ program to count the pairs
// whose sum of digits is co-prime
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Recursive function to return the frequency
// of numbers having their sum of digits i
ll recursive(ll idx, ll sum, ll tight, string st,
             ll dp[20][2][166], ll num)
{
    if (idx == num)
        // Returns 1 or 0
        return sum == 0;
 
    // Returns value of the dp if already stored
    if (dp[idx][tight][sum] != -1)
        return dp[idx][tight][sum];
 
    bool newTight;
    ll ans = 0;
    ll d;
 
    // Loop from digit 0 to 9
    for (d = 0; d < 10; ++d) {
        newTight = false;
        if (tight && st[idx] - '0' < d)
            continue;
 
        // To change the tight to 1
        if (tight && st[idx] - '0' == d)
            newTight = true;
 
        // Calling the recursive function to find the frequency
        if (sum >= d)
            ans += recursive(idx + 1, sum - d,
                             newTight, st, dp, num);
    }
 
    return dp[idx][tight][sum] = ans;
}
 
// Function to find out frequency of numbers
// from 1 to N having their sum of digits
// from 1 to 162 and store them in array
vector<ll> formArray(ll N)
{
    ll dp[20][2][166];
    memset(dp, -1, sizeof dp);
 
    // Number to string conversion
    ostringstream x;
    x << N;
    string st = x.str();
    ll num = st.size();
 
    vector<ll> arr;
    for (int i = 1; i <= 162; ++i) {
 
        // Calling the recursive function
        // and pushing it into array
        arr.push_back(recursive(0, i, 1, st, dp, num));
    }
 
    return arr;
}
 
// Function to find the pairs
ll findPair(ll a, ll b)
{
    // Calling the  formArray function of a-1 numbers
    vector<ll> arr_smaller = formArray(a - 1);
 
    // Calling the  formArray function of b numbers
    vector<ll> arr_greater = formArray(b);
 
    // Subtracting the frequency of higher number array with lower
    // number array and thus finding the range of
    // numbers from a to b having sum from 1 to 162
    for (int i = 0; i < arr_greater.size(); ++i)
        arr_greater[i] -= arr_smaller[i];
 
    int ans = 0;
    for (int i = 1; i <= 162; ++i) {
        for (int j = i + 1; j <= 162; ++j) {
 
            // To find out total number of pairs
            // which are co-prime
            if (__gcd(i, j) == 1)
                ans = (ans + arr_greater[i - 1] * arr_greater[j - 1]);
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    ll a = 12, b = 15;
 
    // Function to count the pairs
    cout << findPair(a, b);
 
    return 0;
}

Java

// Java program to count the pairs
// whose sum of digits is co-prime
import java.io.*;
import java.util.*;
class GFG
{
 
  static int gcd(int a, int b)
  {
    if (b == 0)
      return a;
    return gcd(b, a % b);        
  }
 
  // Recursive function to return the frequency
  // of numbers having their sum of digits i
  static long recursive(long idx, long sum, long tight,
                        String st, long[][][] dp, long num)
  {
    if (idx == num)
    {
 
      // Returns 1 or 0
      return sum == 0 ? 1 : 0;
    }
 
    // Returns value of the dp if already stored
    if (dp[(int)idx][(int)tight][(int)sum] != -1)
      return dp[(int)idx][(int)tight][(int)sum];
 
    long newTight;
    long ans = 0;
    long d;
 
    // Loop from digit 0 to 9
    for (d = 0; d < 10; ++d)
    {
      newTight = 0;
      if (tight == 1 && st.charAt((int)idx) - '0' < d)
        continue;
 
      // To change the tight to 1
      if (tight == 1 && st.charAt((int)idx) - '0' == d)
        newTight = 1;
 
      // Calling the recursive function to find the frequency
      if (sum >= d)
        ans += recursive(idx + 1, sum - d,
                         (int)newTight, st, dp, num);
    }
    return dp[(int)idx][(int)tight][(int)sum] = ans;
  }
 
  // Function to find out frequency of numbers
  // from 1 to N having their sum of digits
  // from 1 to 162 and store them in array
  static ArrayList<Long> formArray(long N)
  {
    long[][][] dp = new long[20][2][166];
    for (long[][] innerRow: dp)
    {
      for (long[] innerInnerRow: innerRow)
      {
        Arrays.fill(innerInnerRow, -1);
      }
    }
 
    // Number to string conversion
    String st = String.valueOf(N);
    long num = st.length();
 
    ArrayList<Long> arr = new ArrayList<Long>();
    for (int i = 1; i <= 162; ++i)
    {
      // Calling the recursive function
      // and pushing it into array
      arr.add(recursive(0, i, 1, st, dp, num));
    }
    return arr;
  }
 
  // Function to find the pairs
  static long findPair(long a, long b)
  {
 
    // Calling the  formArray function of a-1 numbers
    ArrayList<Long> arr_smaller = formArray(a - 1);
 
    // Calling the  formArray function of b numbers
    ArrayList<Long> arr_greater = formArray(b);
 
    // Subtracting the frequency of higher number array with lower
    // number array and thus finding the range of
    // numbers from a to b having sum from 1 to 162
    for (int i = 0; i < arr_greater.size(); ++i)
    {
      arr_greater.set(i,arr_greater.get(i)-arr_smaller.get(i));
    }
    long ans = 0;
    for (int i = 1; i <= 162; ++i)
    {
      for (int j = i + 1; j <= 162; ++j)
      {
        // To find out total number of pairs
        // which are co-prime
        if (gcd(i, j) == 1)
        {
          ans = (ans + arr_greater.get(i-1) * arr_greater.get(j-1));
        }
      }
    }
    return ans;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    long a = 12, b = 15;
 
    // Function to count the pairs
    System.out.println(findPair(a, b));
  }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 program to count
# the pairs whose sum of
# digits is co-prime
import math
 
# Recursive function to
# return the frequency of
# numbers having their sum
# of digits i
def recursive(idx, sum,
              tight, st,
              dp, num):
 
    if (idx == num):
       
        # Returns 1 or 0
        return sum == 0
 
    # Returns value of the dp
    # if already stored
    if (dp[idx][tight][sum] != -1):
        return dp[idx][tight][sum]
 
    ans = 0
 
    # Loop from digit 0 to 9
    for d in range(10):
        newTight = False
        if (tight and ord(st[idx]) -
            ord('0') < d):
            continue
 
        # To change the tight to 1
        if (tight and ord(st[idx]) -
            ord('0') == d):
            newTight = True
 
        # Calling the recursive
        # function to find the
        # frequency
        if (sum >= d):
            ans += recursive(idx + 1,
                             sum - d,
                             newTight,
                             st, dp, num)
 
    dp[idx][tight][sum] = ans
    return dp[idx][tight][sum]
 
# Function to find out frequency
# of numbers from 1 to N having
# their sum of digits from 1 to
# 162 and store them in array
def formArray(N):
 
    dp = [[[-1 for x in range(166)]
               for y in range(2)]
               for z in range(20)]
 
    # Number to string conversion
    st = str(N)
    num = len(st)
 
    arr = []
    for i in range(1, 163):
 
        # Calling the recursive function
        # and pushing it into array
        arr.append(recursive(0, i, 1,
                             st, dp, num))
    return arr
 
# Function to find the pairs
def findPair(a, b):
 
    # Calling the  formArray
    # function of a-1 numbers
    arr_smaller = formArray(a - 1)
 
    # Calling the  formArray
    # function of b numbers
    arr_greater = formArray(b)
 
    # Subtracting the frequency of
    # higher number array with lower
    # number array and thus finding
    # the range of numbers from a to
    # b having sum from 1 to 162
    for i in range(len(arr_greater)):
        arr_greater[i] -= arr_smaller[i]
 
    ans = 0
    for i in range(1, 163):
        for j in range(i + 1, 163):
 
            # To find out total number
            # of pairs which are co-prime
            if (math.gcd(i, j) == 1):
                ans = (ans + arr_greater[i - 1] *
                       arr_greater[j - 1])
    return ans
 
# Driver code
if __name__ == "__main__":
    a = 12
    b = 15
 
    # Function to count the pairs
    print(findPair(a, b))
 
# This code is contributed by Chitranayal

C#

// C# program to count the pairs
// whose sum of digits is co-prime
using System;
using System.Collections.Generic;
 
class GFG{
     
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);        
}
  
// Recursive function to return the frequency
// of numbers having their sum of digits i
static long recursive(long idx, long sum, long tight,
                      string st, long[,,] dp, long num)
{
    if (idx == num)
    {
         
        // Returns 1 or 0
        return sum == 0 ? 1 : 0;
    }
     
    // Returns value of the dp if already stored
    if (dp[(int)idx, (int)tight, (int)sum] != -1)
        return dp[(int)idx, (int)tight, (int)sum];
     
    long newTight;
    long ans = 0;
    long d;
     
    // Loop from digit 0 to 9
    for (d = 0; d < 10; ++d)
    {
        newTight = 0;
         
        if (tight == 1 && st[((int)idx)] - '0' < d)
            continue;
         
        // To change the tight to 1
        if (tight == 1 && st[((int)idx)] - '0' == d)
            newTight = 1;
         
        // Calling the recursive function to
        // find the frequency
        if (sum >= d)
            ans += recursive(idx + 1, sum - d,
                   (int)newTight, st, dp, num);
    }
    return dp[(int)idx, (int)tight, (int)sum] = ans;
}
  
// Function to find out frequency of numbers
// from 1 to N having their sum of digits
// from 1 to 162 and store them in array
static List<long> formArray(long N)
{
    long[,,] dp = new long[20, 2, 166];
    for(int i = 0; i < 20; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 166; k++)
            {
                dp[i, j, k] = -1;
            }
        }
    }
     
    // Number to string conversion
    string st = N.ToString();
    long num = st.Length;
     
    List<long> arr = new List<long>();
    for (int i = 1; i <= 162; ++i)
    {
         
        // Calling the recursive function
        // and pushing it into array
        arr.Add(recursive(0, i, 1, st, dp, num));
    }
    return arr;
}
 
// Function to find the pairs
static long findPair(long a, long b)
{
 
    // Calling the  formArray function of a-1 numbers
    List<long> arr_smaller = formArray(a - 1);
     
    // Calling the  formArray function of b numbers
    List<long> arr_greater = formArray(b);
     
    // Subtracting the frequency of higher number
    // array with lower number array and thus
    // finding the range of numbers from a to b
    // having sum from 1 to 162
    for(int i = 0; i < arr_greater.Count; ++i)
    {
        arr_greater[i] = arr_greater[i] -
                         arr_smaller[i];
    }
    long ans = 0;
     
    for(int i = 1; i <= 162; ++i)
    {
        for(int j = i + 1; j <= 162; ++j)
        {
             
            // To find out total number of pairs
            // which are co-prime
            if (gcd(i, j) == 1)
            {
                ans = (ans + arr_greater[i - 1] *
                             arr_greater[j - 1]);
            }
        }
    }
    return ans;
}
 
// Driver code
static public void Main()
{
    long a = 12, b = 15;
     
    // Function to count the pairs
    Console.WriteLine(findPair(a, b));
}
}
 
// This code is contributed by rag2127

Javascript

<script>
// Javascript program to count the pairs
// whose sum of digits is co-prime
 
function gcd(a,b)
{
    if (b == 0)
      return a;
    return gcd(b, a % b);     
}
 
// Recursive function to return the frequency
// of numbers having their sum of digits i
function recursive(idx,sum,tight,st,dp, num)
{
    if (idx == num)
    {
  
      // Returns 1 or 0
      return sum == 0 ? 1 : 0;
    }
  
    // Returns value of the dp if already stored
    if (dp[idx][tight][sum] != -1)
      return dp[idx][tight][sum];
  
    let newTight;
    let ans = 0;
    let d;
  
    // Loop from digit 0 to 9
    for (d = 0; d < 10; ++d)
    {
      newTight = 0;
      if (tight == 1 && st[idx].charCodeAt(0) - '0'.charCodeAt(0) < d)
        continue;
  
      // To change the tight to 1
      if (tight == 1 && st[idx].charCodeAt(0) - '0'.charCodeAt(0) == d)
        newTight = 1;
  
      // Calling the recursive function to find the frequency
      if (sum >= d)
        ans += recursive(idx + 1, sum - d,
                         newTight, st, dp, num);
    }
    return dp[idx][tight][sum] = ans;
}
 
// Function to find out frequency of numbers
  // from 1 to N having their sum of digits
  // from 1 to 162 and store them in array
function formArray(N)
{
    let dp = new Array(20);
    for(let i=0;i<20;i++)
    {
        dp[i]=new Array(2);
        for(let j=0;j<2;j++)
        {
            dp[i][j]=new Array(166);
            for(let k=0;k<166;k++)
            {
                dp[i][j][k]=-1;
            }
        }
    }
  
    // Number to string conversion
    let st = (N).toString();
    let num = st.length;
  
    let arr = [];
    for (let i = 1; i <= 162; ++i)
    {
      // Calling the recursive function
      // and pushing it into array
      arr.push(recursive(0, i, 1, st, dp, num));
    }
    return arr;
}
 
// Function to find the pairs
function findPair(a,b)
{
    // Calling the  formArray function of a-1 numbers
    let arr_smaller = formArray(a - 1);
  
    // Calling the  formArray function of b numbers
    let arr_greater = formArray(b);
  
    // Subtracting the frequency of higher number array with lower
    // number array and thus finding the range of
    // numbers from a to b having sum from 1 to 162
    for (let i = 0; i < arr_greater.length; ++i)
    {
      arr_greater[i] -= arr_smaller[i];
    }
    let ans = 0;
    for (let i = 1; i <= 162; ++i)
    {
      for (let j = i + 1; j <= 162; ++j)
      {
        // To find out total number of pairs
        // which are co-prime
        if (gcd(i, j) == 1)
        {
          ans = (ans + arr_greater[i-1] * arr_greater[j-1]);
        }
      }
    }
    return ans;
}
 
// Driver code
let a = 12, b = 15;
  
// Function to count the pairs
document.write(findPair(a, b));
 
 
// This code is contributed by ab2127
</script>
Producción: 

4

 

Publicación traducida automáticamente

Artículo escrito por atulim y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *