HackerRank Clique problem solution

In this HackerRank Clique problem solution, A clique in a graph is a set of nodes such that there is an edge between any two distinct nodes in the set. Finding the largest clique in a graph is a computationally difficult problem. Currently, no polynomial-time algorithm is known for solving this. However, you wonder what is the minimum size of the largest clique in any graph with n nodes and m edges.

Problem solution in Python.

```#!/bin/python3

import os
import sys
import math

#
# Complete the clique function below.
#
def clique(n, m):
low = 1
high = n
while low + 1 < high:
mid = (low + high) // 2
tedges = int(turan(n, mid))
if tedges < m:
low = mid
else:
high = mid
return high

def turan(n, k):
return (n ** 2 - (n % k) * ((math.ceil(n / k)) ** 2) - (k - (n % k)) * ((n // k) ** 2)) // 2

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input())

for t_itr in range(t):
nm = input().split()

n = int(nm[0])

m = int(nm[1])

result = clique(n, m)
fptr.write(str(result) + '\n')
print(result)

fptr.close()
```

{"mode":"full","isActive":false}

Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();

for (int i=0; i<t; i++) {
int n = scan.nextInt();
int m = scan.nextInt();

int k = 1;
while (k<n && turan(n,k+1)<m)
k++;
System.out.println(k);
}
}

// returns the maximum number of edges on a graph of size n without producing k-clique
static int turan(int n, int k) {
int b = n%(k-1);    // # of larger independent sets
int a = k-1-b;      // # of smaller independent sets
int j = n/(k-1);    // size of smaller sets
return j*j*a*(a-1)/2+j*(j+1)*a*b+(j+1)*(j+1)*b*(b-1)/2;
}
}```

{"mode":"full","isActive":false}

Problem solution in C++.

```#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <list>
#include <cstring>
#include <stack>
#include <bitset>

using namespace std;

#define NMAX 2147483647
#define LMAX 9223372036854775807LL
#define pb push_back
#define pob pop_back
#define mp make_pair
#define st first
#define nd second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a);i>(b);--i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)

int solve1(int n,int k)
{
int g1 = n%k ;
int g2 = k - g1 ;
int sz1 = n/k + 1 ;
int sz2 = n/k ;
int ret = g1*sz1*g2*sz2 + g1*(g1-1)*sz1*sz1/2 + g2*(g2-1)*sz2*sz2/2 ;
return ret ;
}

int solve(int n,int e)
{
int k,low = 1,high = n + 1 ;
while(low + 1 < high)
{
int mid = low + (high - low)/2 ;
k = solve1(n,mid) ;
if(k < e) low = mid ;
else high = mid ;
}
return high ;
}

int main()
{
//freopen("input.txt","r",stdin);
//freopen("out.txt","w",stdout);
int TS;
scanf("%d",&TS);
FORE(ts,1,TS)
{
int N, M;
scanf("%d%d",&N,&M);
printf("%d\n",solve(N,M));
}
return 0;
}
```

{"mode":"full","isActive":false}

Problem solution in C.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int formula(unsigned int vertices, unsigned int k) {
int squared = vertices * vertices;
int clique_mod = vertices % k;
int upper = ceil((double)vertices/(double)k);
int lower = floor((double)vertices/(double)k);

return (squared - (clique_mod * upper * upper) - (k - clique_mod)* lower * lower) / 2;
}

int main() {
unsigned int cases, vertices, edges;
int k;

scanf("%u", &cases);

while(cases--) {
scanf("%u %u", &vertices, &edges);

int min = 1;
int max = vertices;
k = (min + max)/2;

while(k <= vertices) {
int f = formula(vertices, k);
int f_plus_1 = formula(vertices, k + 1);

if (edges > f) {
if (edges <= f_plus_1) {
printf("%d\n", k+1);
break;
}

min = k + 1;
} else {
max = k - 1;
}

k = (min + max)/2;
}
}

return 0;
}
```

{"mode":"full","isActive":false}