Рубрики

Возможны два набора из первых N натуральных чисел разницы сумм как D

Учитывая N и D, найдите, возможно ли сделать два набора из первых N натуральных чисел так, чтобы разница между суммой двух наборов (по отдельности) составляла D.


Примеры :

Input  : 5 7
Output : yes
Explanation: Keeping 1 and 3 in one set,
and 2, 4 and 5 are in other set.
Sum of set 1 = 4
Sum of set 2 = 11 
So, the difference D = 7 
Which is the required difference

Input  : 4 5
Output : no

Подходить :

Let s1 and s2 be the two sets.
Here we know that
sum(s1) + sum(s2) = N*(N+1)/2 and
sum(s1) – sum(s2) = D

Adding above 2 equations, we get
2*sum(s1) = N*(N+1)/2 + D

If sum(S1) and sum(S2) are integers, then only we can split the first N natural numbers into two sets. For that N*(N+1)/2 + D must be an even number.

C ++

// C ++ программа для реализации
// вышеуказанный подход
#include <bits/stdc++.h>

using namespace std;

  
// Функция возвращает true, если это
// можно разбить на две части
// устанавливает иначе возвращает false

bool check(int N, int D)

{    

    int temp = (N * (N + 1)) / 2 + D;

    return (temp % 2 == 0);

}

  
// Код драйвера

int main()

{

    int N = 5;

    int M = 7;

    if (check(N, M))

        cout << "yes";

    else

        cout << "no";

  

    return 0;

}

Джава

// Java-программа для реализации
// вышеуказанный подход

  

class GFG

{

      

    // Функция возвращает true, если это

    // можно разбить на две части

    // устанавливает иначе возвращает false

    static boolean check(int N, int D)

    

        int temp = (N * (N + 1)) / 2 + D;

        return (temp % 2 == 0);

    }

      

    // Код драйвера

    static public void main (String args[])

    {

        int N = 5;

        int M = 7;

        if (check(N, M))

            System.out.println("yes");

        else

            System.out.println("no");

    }

}

  
// Этот код предоставлен Smitha.

python3

# Python программа для реализации
# выше подход

  
# Функция возвращает true, если это
# можно разделить на две части
# устанавливает в противном случае возвращает false

def check(N, D):

    temp = N * (N + 1) // 2 + D

    return (bool(temp % 2 == 0))

  
# Код драйвера

N = 5

M = 7

if check(N, M):

    print("yes")

else:

    print("no")

  
# Этот код предоставлен Shrikant13.

C #

// C # программа для реализации
// вышеуказанный подход

using System;

  

class GFG

{

      

    // Функция возвращает true, если это

    // можно разбить на две части

    // устанавливает иначе возвращает false

    static bool check(int N, int D)

    

        int temp = (N * (N + 1)) / 2 + D;

        return (temp % 2 == 0);

    }

      

    // Код драйвера

    static public void Main ()

    {

        int N = 5;

        int M = 7;

        if (check(N, M))

            Console.Write("yes");

        else

            Console.Write("no");

    }

}

  
// Этот код предоставлен Ajit.

PHP

<?php
// PHP программа для реализации
// вышеуказанный подход

  
// Функция возвращает true, если это
// можно разбить на две части
// устанавливает иначе возвращает false

function check($N, $D)

    $temp = ($N * ($N + 1)) / 2 + $D;

    return ($temp % 2 == 0);

}

  
// Код драйвера

$N = 5;

$M = 7;

if (check($N, $M))

    echo("yes");

else

    echo("no");

  
// Этот код предоставлен Ajit.

ВЫХОД :

yes

Рекомендуемые посты:

Возможны два набора из первых N натуральных чисел разницы сумм как D

0.00 (0%) 0 votes