Dado un entero K , la tarea es encontrar la longitud del número más pequeño. N que es divisible por K y se forma usando 1 como sus dígitos únicamente. Si no existe tal número, imprima -1
Ejemplos:
Entrada: K = 3
Salida: 3
111 es el número más pequeño formado usando solo 1
que es divisible por 3.
Entrada: K = 7
Salida: 6
111111 es el número requerido.
Entrada: K = 12
Salida: -1
Enfoque ingenuo:
- Primero tenemos que verificar si K es un múltiplo de 2 o 5 , entonces la respuesta será -1 porque no hay un número formado usando solo 1 como sus dígitos, que es divisible por 2 o 5 .
- Ahora iterar para cada posible no. formado usando 1 como máximo K veces y verifica su divisibilidad con K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return length
// of the resultant number
int numLen(int K)
{
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0)
return -1;
int number = 0;
int len = 1;
for (len = 1; len <= K; len++) {
// Generate all possible numbers
// 1, 11, 111, 111, ..., K 1's
number = number * 10 + 1;
// If number is divisible by k
// then return the length
if ((number % K == 0))
return len;
}
return -1;
}
// Driver code
int main()
{
int K = 7;
cout << numLen(K);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return length
// of the resultant number
static int numLen(int K)
{
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0)
{
return -1;
}
int number = 0;
int len = 1;
for (len = 1; len <= K; len++)
{
// Generate all possible numbers
// 1, 11, 111, 111, ..., K 1's
number = number * 10 + 1;
// If number is divisible by k
// then return the length
if ((number % K == 0))
{
return len;
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int K = 7;
System.out.println(numLen(K));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python implementation of the approach # Function to return length # of the resultant number def numLen(K): # If K is a multiple of 2 or 5 if (K % 2 == 0 or K % 5 == 0): return -1; number = 0; len = 1; for len in range(1,K+1): # Generate all possible numbers # 1, 11, 111, 111, ..., K 1's number = number * 10 + 1; # If number is divisible by k # then return the length if ((number % K == 0)): return len; return -1; # Driver code K = 7; print(numLen(K)); # This code contributed by Rajput-Ji
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return length
// of the resultant number
static int numLen(int K)
{
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0)
return -1;
int number = 0;
int len = 1;
for (len = 1; len <= K; len++)
{
// Generate all possible numbers
// 1, 11, 111, 111, ..., K 1's
number = number * 10 + 1;
// If number is divisible by k
// then return the length
if ((number % K == 0))
return len;
}
return -1;
}
// Driver code
static void Main()
{
int K = 7;
Console.WriteLine(numLen(K));
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
// Function to return length
// of the resultant number
function numLen($K)
{
// If K is a multiple of 2 or 5
if ($K % 2 == 0 || $K % 5 == 0)
return -1;
$number = 0;
$len = 1;
for ($len = 1; $len <= $K; $len++)
{
// Generate all possible numbers
// 1, 11, 111, 111, ..., K 1's
$number = $number * 10 + 1;
// If number is divisible by k
// then return the length
if (($number % $K == 0))
return $len;
}
return -1;
}
// Driver code
$K = 7;
echo numLen($K);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// javascript implementation of the approach
// Function to return length
// of the resultant number
function numLen(K) {
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0) {
return -1;
}
var number = 0;
var len = 1;
for (len = 1; len <= K; len++)
{
// Generate all possible numbers
// 1, 11, 111, 111, ..., K 1's
number = number * 10 + 1;
// If number is divisible by k
// then return the length
if ((number % K == 0)) {
return len;
}
}
return -1;
}
// Driver code
var K = 7;
document.write(numLen(K));
// This code is contributed by Princi Singh
</script>
Producción:
6
Complejidad de tiempo: O(K)
Espacio Auxiliar: O(1)
Enfoque eficiente: como vemos en el enfoque anterior, generamos todos los números posibles como 1, 11, 1111, 11111, …, K veces, pero si el valor de K es muy grande, entonces el no. estará fuera del rango del tipo de datos para que podamos hacer uso de las propiedades modulares.
En lugar de hacer número = número * 10 + 1 , podemos hacerlo mejor como número = (número * 10 + 1) % K
Explicación: comenzamos con número = 1 y repetidamente hacemos número = número * 10 + 1 luego en cada iteración Obtendrá un nuevo término de la secuencia anterior.
1*10 + 1 = 11
11*10 + 1 = 111
111*10 + 1 = 1111
1111*10 + 1 = 11111
11111*10 + 1 = 111111
Dado que estamos tomando repetidamente los restos del número en cada paso, en cada paso tenemos, newNum = oldNum * 10 + 1. Según las reglas de la aritmética modular (a * b + c) % m es lo mismo que ((a * b) % m + c % m) % m . Entonces, no importa si oldNum es el resto o el número original, la respuesta sería correcta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return length
// of the resultant number
int numLen(int K)
{
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0)
return -1;
int number = 0;
int len = 1;
for (len = 1; len <= K; len++) {
// Instead of generating all possible numbers
// 1, 11, 111, 111, ..., K 1's
// Take remainder with K
number = (number * 10 + 1) % K;
// If number is divisible by k
// then remainder will be 0
if (number == 0)
return len;
}
return -1;
}
// Driver code
int main()
{
int K = 7;
cout << numLen(K);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to return length
// of the resultant number
public static int numLen(int K)
{
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0)
return -1;
int number = 0;
int len = 1;
for (len = 1; len <= K; len++) {
// Instead of generating all possible numbers
// 1, 11, 111, 111, ..., K 1's
// Take remainder with K
number = (number * 10 + 1) % K;
// If number is divisible by k
// then remainder will be 0
if (number == 0)
return len;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int K = 7;
System.out.print(numLen(K));
}
}
Python3
# Python3 implementation of the approach # Function to return length # of the resultant number def numLen(K): # If K is a multiple of 2 or 5 if(K % 2 == 0 or K % 5 == 0): return -1 number = 0 len = 1 for len in range (1, K + 1): # Instead of generating all possible numbers # 1, 11, 111, 111, ..., K 1's # Take remainder with K number = ( number * 10 + 1 ) % K # If number is divisible by k # then remainder will be 0 if number == 0: return len return -1 # Driver code K = 7 print(numLen(K))
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return length
// of the resultant number
public static int numLen(int K)
{
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0)
return -1;
int number = 0;
int len = 1;
for (len = 1; len <= K; len++)
{
// Instead of generating all possible numbers
// 1, 11, 111, 111, ..., K 1's
// Take remainder with K
number = (number * 10 + 1) % K;
// If number is divisible by k
// then remainder will be 0
if (number == 0)
return len;
}
return -1;
}
// Driver code
public static void Main()
{
int K = 7;
Console.WriteLine(numLen(K));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return length
// of the resultant number
function numLen($K)
{
// If K is a multiple of 2 or 5
if ($K % 2 == 0 || $K % 5 == 0)
return -1;
$number = 0;
$len = 1;
for ($len = 1; $len <= $K; $len++)
{
// Instead of generating all possible numbers
// 1, 11, 111, 111, ..., K 1's
// Take remainder with K
$number = ($number * 10 + 1) % $K;
// If number is divisible by k
// then remainder will be 0
if ($number == 0)
return $len;
}
return -1;
}
// Driver code
$K = 7;
echo numLen($K);
// This code is contributed by mits
?>
Javascript
<script>
// javascript implementation of the approach
// Function to return length
// of the resultant number
function numLen(K)
{
// If K is a multiple of 2 or 5
if (K % 2 == 0 || K % 5 == 0)
return -1;
var number = 0;
var len = 1;
for (len = 1; len <= K; len++) {
// Instead of generating all possible numbers
// 1, 11, 111, 111, ..., K 1's
// Take remainder with K
number = (number * 10 + 1) % K;
// If number is divisible by k
// then remainder will be 0
if (number == 0)
return len;
}
return -1;
}
// Driver code
var K = 7;
document.write(numLen(K));
// This code contributed by shikhasingrajput
</script>
Producción:
6
Complejidad temporal: O(K)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA