Dado un número entero no negativo N , la tarea es verificar si ese número entero se puede representar como una suma de múltiplos de 3, 5 y 7, e imprimir sus valores respectivos. Si la tarea no es posible, imprima -1.
Ejemplos:
Entrada: 10
Salida: 1 0 1
Explicación: 10 se puede representar como: (3 * 1) + (5 * 0) + (7 * 1) = 10. Otra representación válida es (3 * 0) + (5 * 2 ) + (7 * 0)Entrada: 4
Salida: -1
Explicación : 4 no se puede representar como una suma de múltiplos de 3, 5 y 7.
Enfoque ingenuo: el problema dado se puede resolver mediante el uso de tres bucles for anidados, para iterar sobre múltiplos de 3, 5 y 7, y realizar un seguimiento de si existe una combinación con suma como N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <iostream>
using namespace std;
// Function to check if a number can
// be represented as summation of the
// multiples of 3, 5 and 7
void check357(int N)
{
// flag indicates if combination
// is possible or not
int flag = 0;
// Loop for multiples of 3
for (int i = 0; i <= N / 3; i++) {
if (flag == 1)
break;
// Loop for multiples of 5
for (int j = 0; j <= N / 5; j++) {
if (flag == 1)
break;
// Loop for multiples of 7
for (int k = 0; k <= N / 7; k++) {
// If sum is N
if (3 * i + 5 * j + 7 * k == N) {
// Combination found
flag = 1;
// Print Answer
cout << i << " "
<< j << " " << k;
break;
}
}
}
}
// No valid combination found
if (flag == 0)
cout << -1;
}
// Driver code
int main()
{
int N = 10;
check357(N);
}
Java
// Java code for the above approach
import java.io.*;
class GFG
{
// Function to check if a number can
// be represented as summation of the
// multiples of 3, 5 and 7
static void check357(int N)
{
// flag indicates if combination
// is possible or not
int flag = 0;
// Loop for multiples of 3
for (int i = 0; i <= N / 3; i++) {
if (flag == 1)
break;
// Loop for multiples of 5
for (int j = 0; j <= N / 5; j++) {
if (flag == 1)
break;
// Loop for multiples of 7
for (int k = 0; k <= N / 7; k++) {
// If sum is N
if (3 * i + 5 * j + 7 * k == N) {
// Combination found
flag = 1;
// Print Answer
System.out.print(i + " " + j + " "
+ k);
break;
}
}
}
}
// No valid combination found
if (flag == 0)
System.out.println(-1);
}
// Driver code
public static void main(String[] args)
{
int N = 10;
check357(N);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python implementation of the above approach
# Function to check if a number can
# be represented as summation of the
# multiples of 3, 5 and 7
def check357(N):
# flag indicates if combination
# is possible or not
flag = 0;
# Loop for multiples of 3
for i in range((N // 3) + 1):
if (flag == 1):
break;
# Loop for multiples of 5
for j in range((N // 5) + 1):
if (flag == 1):
break;
# Loop for multiples of 7
for k in range((N // 7) + 1):
# If sum is N
if (3 * i + 5 * j + 7 * k == N):
# Combination found
flag = 1;
# Print Answer
print(f"{i} {j} {k}");
break;
# No valid combination found
if (flag == 0):
print(-1);
# Driver code
N = 10;
check357(N);
# This code is contributed by saurabh_jaiswal.
C#
// C# code for the above approach
using System;
public class GFG
{
// Function to check if a number can
// be represented as summation of the
// multiples of 3, 5 and 7
static void check357(int N)
{
// flag indicates if combination
// is possible or not
int flag = 0;
// Loop for multiples of 3
for (int i = 0; i <= N / 3; i++) {
if (flag == 1)
break;
// Loop for multiples of 5
for (int j = 0; j <= N / 5; j++) {
if (flag == 1)
break;
// Loop for multiples of 7
for (int k = 0; k <= N / 7; k++) {
// If sum is N
if (3 * i + 5 * j + 7 * k == N) {
// Combination found
flag = 1;
// Print Answer
Console.Write(i + " " + j + " " + k);
break;
}
}
}
}
// No valid combination found
if (flag == 0)
Console.WriteLine(-1);
}
// Driver code
public static void Main(string[] args)
{
int N = 10;
check357(N);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript implementation of the above approach
// Function to check if a number can
// be represented as summation of the
// multiples of 3, 5 and 7
function check357(N)
{
// flag indicates if combination
// is possible or not
let flag = 0;
// Loop for multiples of 3
for (let i = 0; i <= Math.floor(N / 3); i++) {
if (flag == 1)
break;
// Loop for multiples of 5
for (let j = 0; j <= Math.floor(N / 5); j++) {
if (flag == 1)
break;
// Loop for multiples of 7
for (let k = 0; k <= Math.floor(N / 7); k++) {
// If sum is N
if (3 * i + 5 * j + 7 * k == N) {
// Combination found
flag = 1;
// Print Answer
document.write(i + " " + j + " " + k);
break;
}
}
}
}
// No valid combination found
if (flag == 0)
document.write(-1);
}
// Driver code
let N = 10;
check357(N);
// This code is contributed by saurabh_jaiswal.
</script>
Producción
0 2 0
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema dado se puede resolver usando las matemáticas .
Dado que todo número se puede representar en términos de múltiplo de 3, como 3x, 3x+1 o 3x+2. Usando este hecho, podemos decir que 5 se puede representar en la forma 3x+2 y 7 se puede representar en la forma 3x+1.
Con la ayuda de esta observación, N se puede representar de las 3 formas siguientes:
- Si N tiene la forma 3x , se puede representar como 3x .
- Si N es de la forma 3x + 1 ,
- Si N > 7 , entonces N se puede representar como 3*(x – 2) + 7 , ya que 7 es similar a 3*2 + 1 .
- De lo contrario, si N <= 7 , entonces no se puede representar en la forma dada.
- Si N es de la forma 3n + 2 ,
- Si N > 5 , entonces N se puede representar como 3x + 5 ya que 5 es similar a 3*1 + 2 .
- De lo contrario, si N <= 5 , entonces no se puede representar en la forma dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number can be
// represented as summation of multiples
// of 3, 5 and 7
int check357(int N)
{
// Stores if a valid
// combination exists
int f = 0;
// if N is of the form 3n
if (N % 3 == 0)
return (N / 3) * 100 + 0 * 10 + 0;
else if (N % 3 == 1) {
// if N is of the form 3n + 1
if (N - 7 >= 0)
return ((N - 7) / 3) * 100 + 0 * 10 + 1;
}
else
// if N is of the form 3n + 2
if (N - 5 >= 0)
return ((N - 5) / 3) * 100 + 1 * 10 + 0;
// If no valid combinations exists
return -1;
}
// Driver code
int main()
{
int N = 10;
cout << check357(N);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
public class GFG
{
// Function to check if a number can be
// represented as summation of multiples
// of 3, 5 and 7
static int check357(int N)
{
// Stores if a valid
// combination exists
int f = 0;
// if N is of the form 3n
if (N % 3 == 0)
return (N / 3) * 100 + 0 * 10 + 0;
else if (N % 3 == 1) {
// if N is of the form 3n + 1
if (N - 7 >= 0)
return ((N - 7) / 3) * 100 + 0 * 10 + 1;
}
else
// if N is of the form 3n + 2
if (N - 5 >= 0)
return ((N - 5) / 3) * 100 + 1 * 10 + 0;
// If no valid combinations exists
return -1;
}
// Driver code
public static void main(String args[])
{
int N = 10;
System.out.print(check357(N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python implementation of the above approach # Function to check if a number can be # represented as summation of multiples # of 3, 5 and 7 def check357(N): # Stores if a valid # combination exists f = 0; # if N is of the form 3n if (N % 3 == 0): return (N // 3) * 100 + 0 * 10 + 0; elif (N % 3 == 1): # if N is of the form 3n + 1 if (N - 7 >= 0): return ((N - 7) // 3) * 100 + 0 * 10 + 1; else: if(N - 5 >= 0): # if N is of the form 3n + 2 return ((N - 5) // 3) * 100 + 1 * 10 + 0; # If no valid combinations exists return -1; # Driver code if __name__ == '__main__': N = 10; print(check357(N)); # This code is contributed by shikhasingrajput
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to check if a number can be
// represented as summation of multiples
// of 3, 5 and 7
static int check357(int N)
{
// Stores if a valid
// combination exists
int f = 0;
// if N is of the form 3n
if (N % 3 == 0)
return (N / 3) * 100 + 0 * 10 + 0;
else if (N % 3 == 1) {
// if N is of the form 3n + 1
if (N - 7 >= 0)
return ((N - 7) / 3) * 100 + 0 * 10 + 1;
}
else
// if N is of the form 3n + 2
if (N - 5 >= 0)
return ((N - 5) / 3) * 100 + 1 * 10 + 0;
// If no valid combinations exists
return -1;
}
// Driver code
public static void Main()
{
int N = 10;
Console.Write(check357(N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript implementation of the above approach
// Function to check if a number can be
// represented as summation of multiples
// of 3, 5 and 7
function check357(N)
{
// Stores if a valid
// combination exists
let f = 0;
// if N is of the form 3n
if (N % 3 == 0)
return (N / 3) * 100 + 0 * 10 + 0;
else if (N % 3 == 1) {
// if N is of the form 3n + 1
if (N - 7 >= 0)
return ((N - 7) / 3) * 100 + 0 * 10 + 1;
}
else
// if N is of the form 3n + 2
if (N - 5 >= 0)
return ((N - 5) / 3) * 100 + 1 * 10 + 0;
// If no valid combinations exists
return -1;
}
// Driver code
let N = 10;
document.write(check357(N));
// This code is contributed by gfgking.
</script>
Producción:
101
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)