Сделайте n, используя единицы и двойки с минимальным количеством членов, кратным k
Даны два натуральных числа n и k . n можно представить как сумму единиц и двоек разными способами, используя несколько чисел. Задача состоит в том, чтобы найти минимальное количество членов из единиц и двоек, которые используются для получения суммы n, а также количество членов, которые должны быть кратны k. Выведите «-1», если такого количества терминов не существует.
Примеры :
Ввод: n = 10, k = 2 Выход: 6 10 можно представить как 2 + 2 + 2 + 2 + 1 + 1. Количество используемых терминов - 6, что кратно 2. Ввод: n = 11, k = 4 Выход: 8 10 можно представить как 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 Количество используемых терминов - 8, что кратно 4.
Observe, the maximum number of terms used to represent n as the sum of 1s and 2s is n, when 1 are added n number of times. Also, the minimum number of terms will be n/2 times of 2s and n%2 times 1s are added. So, iterate from minimum number of terms to maximum number of terms and check if there is any multiple of k.
C++
// C++ program to find minimum multiple of k// terms used to make sum n using 1s and 2s.#include<bits/stdc++.h>using namespace std;// Return minimum multiple of k terms used to// make sum n using 1s and 2s.int minMultipleK(int n, int k){ // Minimum number of terms required to make // sum n using 1s and 2s. int min = (n / 2) + (n % 2); // Iterate from Minimum to maximum to find // multiple of k. Maximum number of terns is // n (Sum of all 1s) for (int i = min; i <= n; i++) if (i % k == 0) return i; return -1;}// Driven Programint main(){ int n = 10, k = 2; cout << minMultipleK(n, k) << endl; return 0;} |
Java
// Java program to find minimum// multiple of k terms used to// make sum n using 1s and 2s.import java.io.*;class GFG{ // Return minimum multiple of// k terms used to make sum n// using 1s and 2s.static int minMultipleK(int n, int k){ // Minimum number of terms // required to make sum n // using 1s and 2s. int min = (n / 2) + (n % 2); // Iterate from Minimum to // maximum to findmultiple of k. // Maximum number of terms is // n (Sum of all 1s) for (int i = min; i <= n; i++) if (i % k == 0) return i; return -1;}// Driver Codepublic static void main (String[] args){ int n = 10, k = 2; System.out.println( minMultipleK(n, k));}}// This code is contributed by anuj_67. |
Python3
# Python3 program to find minimum multiple of k# terms used to make sum n using 1s and 2s.# Return minimum multiple of k terms# used to make sum n using 1s and 2s.def minMultipleK( n, k): # Minimum number of terms required # to make sum n using 1s and 2s. min = (n // 2) + (n % 2) # Iterate from Minimum to maximum to find #multiple of k. Maximum number of terns is # n (Sum of all 1s) for i in range(min, n + 1): if (i % k == 0): return i return -1# Driver Codeif __name__=="__main__": n = 10 k = 2 print (minMultipleK(n, k)) # This code is contributed# by ChitraNayal |
C#
// C# program to find minimum// multiple of k terms used to// make sum n using 1s and 2s.using System;class GFG{ // Return minimum multiple of// k terms used to make sum n// using 1s and 2s.static int minMultipleK(int n, int k){ // Minimum number of terms // required to make sum n // using 1s and 2s. int min = (n / 2) + (n % 2); // Iterate from Minimum to // maximum to findmultiple of k. // Maximum number of terms is // n (Sum of all 1s) for (int i = min; i <= n; i++) if (i % k == 0) return i; return -1;}// Driver Codepublic static void Main (){ int n = 10, k = 2; Console.WriteLine( minMultipleK(n, k));}}// This code is contributed by anuj_67. |
PHP
<?php// PHP program to find minimum multiple of// k terms used to make sum n using 1s and 2s.// Return minimum multiple of k terms used// to make sum n using 1s and 2s.function minMultipleK($n, $k) { // Minimum number of terms required // to make sum n using 1s and 2s. $min = ($n / 2) + ($n % 2); // Iterate from Minimum to maximum to // findmultiple of k. Maximum number // of terms is n (Sum of all 1s) for ($i = $min; $i <= $n; $i++) if ($i % $k == 0) return $i; return -1;}// Driver Code$n = 10; $k = 2;echo(minMultipleK($n, $k));// This code is contributed// by Mukul singh. |
Javascript
<script>// JavaScript program for the above approach // Return minimum multiple of// k terms used to make sum n// using 1s and 2s.function minMultipleK(n, k){ // Minimum number of terms // required to make sum n // using 1s and 2s. let min = (n / 2) + (n % 2); // Iterate from Minimum to // maximum to findmultiple of k. // Maximum number of terms is // n (Sum of all 1s) for (let i = min; i <= n; i++) if (i % k == 0) return i; return -1;}// Driver Code let n = 10, k = 2; document.write( minMultipleK(n, k)); // This code is contributed by splevel62.</script> |
Выход :
6
Автор статьи - Анудж Чаухан . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.