Moneda de Filadelfia | TCS Mockvita 2020

Descripción del problema

Los solucionadores de problemas encontraron una nueva isla para codificar y la llamaron Philaland. A estas personas inteligentes se les asignó la tarea de facilitar la compra de artículos en la isla mediante la distribución de varias monedas con diferentes valores. A Manish se le ocurrió una solución: si creamos una categoría de monedas desde $1 hasta el precio máximo del artículo presente en Island, entonces podemos comprar cualquier artículo fácilmente. Agregó el siguiente ejemplo para probar su punto. 

Supongamos que el precio máximo de un artículo es 5 $, entonces podemos hacer monedas de {$1, $2, $3, $4, $5} para comprar cualquier artículo que va desde $1 hasta $5. Ahora, Manisha, siendo una observadora entusiasta, sugirió que en realidad podríamos minimizar la cantidad de monedas requeridas y dio la siguiente distribución {$1, ​​$2, $3}. Según él, cualquier artículo se puede comprar una vez y oscila entre $1 y $5. Todos quedaron impresionados con ambos.

Su tarea es ayudar a Manisha a encontrar la cantidad mínima de denominaciones para cualquier precio máximo arbitrario en Filadelfia.

Ejemplos:

Entrada: N = 10
Salida: 4
Explicación:
Según Manish, se debe distribuir {$1, ​​$2, $3, … $10}.
Pero según Manisha, solo {$1, $2, $3, $4} monedas son suficientes para comprar cualquier artículo que va desde $1 a $10. Por lo tanto, el mínimo es 4. Del mismo modo, las denominaciones también podrían ser {$1, ​​$2, $3, $5}. Por lo tanto, la respuesta sigue siendo 4.

Entrada: N = 5
Salida: 3
Explicación:
Según Manish {$1, ​​$2, $3, $4, $5} deben distribuirse.
Pero según Manisha, solo {$1, $2, $3} monedas son suficientes para comprar cualquier artículo que varíe de $1 a $5. Por lo tanto, el mínimo es 3. Del mismo modo, las denominaciones también podrían ser {$1, ​​$2, $4}. Por lo tanto, la respuesta sigue siendo 3.

Enfoque: La observación clave del problema es que cualquier número puede representarse como las potencias dos . Por lo tanto, el número mínimo de denominación requerida es:

Por ejemplo:

Para N = 12, 
si elegimos las denominaciones como {1, 2, 4, 8},
entonces cada número hasta 12 se puede representar como:

1 ==> 1
2 ==> 2
3 ==> 2 + 1
4 ==> 4
5 ==> 4 + 1
6 ==> 4 + 2
7 ==> 4 + 2 + 1
8 ==> 8
9 ==> 8 + 1
10 ==> 8 + 2
11 ==> 8 + 2 + 1
12 ==> 8 + 4

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

// C++ implementation to find the
// minimum number of denominations
// required for any number
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number of denomminations required
int findMinDenomin(int n)
{
    return log2(n) + 1;
}
 
// Driver Code
int main()
{
    int n = 10;
 
    // Function Call
    cout << findMinDenomin(n);
    return 0;
}

// Java implementation to find the
// minimum number of denominations
// required for any number
import java.io.*;
class GFG
{
   
    // Function to find the minimum
    // number of denomminations required
    static int findMinDenomin(int n)
    {
        return ((int)(Math.log(n)/Math.log(2))+1);
    }
   
    // Driver Code
    public static void main (String[] args)
    {
        int n = 10;
       
        // Function Call
        System.out.println(findMinDenomin(n));
    }
}
 
//  This code is contributed by avanitrachhadiya2155

# Python3 implementation to find the
# minimum number of denominations
# required for any number
from math import log2, floor
 
# Function to find the minimum
# number of denomminations required
def findMinDenomin(n):
 
    return log2(n) + 1
 
# Driver Code
if __name__ == '__main__':
     
    n = 10
 
    # Function call
    print(floor(findMinDenomin(n)))
 
# This code is contributed by mohit kumar 29

// C# implementation to find the
// minimum number of denominations
// required for any number
using System;
class GFG
{
 
  // Function to find the minimum
  // number of denomminations required
  static int findMinDenomin(int n)
  {
    return ((int)(Math.Log(n)/Math.Log(2))+1);
  }
 
  // Driver Code
  static public void Main ()
  {
    int n = 10;
 
    // Function Call
    Console.WriteLine(findMinDenomin(n));
  }
}
 
// This code is contributed by rag2127

<script>
// Javascript implementation to find the
// minimum number of denominations
// required for any number
 
// Function to find the minimum
// number of denomminations required
function findMinDenomin(n)
{
        return (Math.floor(Math.log(n)/Math.log(2)) + 1);
}
 
// Driver Code
let n = 10;
 
 // Function Call
document.write(findMinDenomin(n));
 
// This code is contributed by patel2127
</script>

4

Análisis de rendimiento:

• Complejidad de tiempo: O (logN)
• Espacio Auxiliar: O(1)