HackerRank Clique Problem Solution

In this post, we will solve HackerRank Clique Problem Solution.

A clique in a graph is 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 nodes and m edges. For example, consider a graph with n = 4 nodes and m = 5 edges. The graph below shows 4 nodes with 4 edges and no cliques. It is evident that the addition of any 5th edge must create two cliques with 3 members each.

Input Format

The first line contains an integer t, the number of test cases.

Each of the next t lines contains two space-separated integers n and m.

Output Format

For each test case, print the minimum size of the largest clique that must be formed given n and m.

Sample Input

Sample Output

2  
4  
3

Explanation

For the first case, we have two cliques with two nodes each:

For the second test case, the only valid graph having 4 nodes and 6 edges is one where each pair of nodes is connected. So the size of the largest clique cannot be smaller than 4.

For the third test case, it is easy to verify that any graph with 5 nodes and 7. The 5 solid lines in the graph below indicate the maximum edges that can be added without forming a clique larger than 2. The dashed lines could connect any two nodes not connected by solid lines producing a clique of size 3.

Clique C Solution

#include<stdio.h>
 
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()
{
 int i,j,n,k,runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d%d",&n,&k) ;
  int ret = solve(n,k) ;
  printf("%d\n",ret) ;
 }
 return 0 ;
}

Clique C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {

int t;
double n, m;
cin>>t;

    for(int i = 0; i < t; i++) {
        cin>>n>>m;
        int x = ceil( ( n * n * (1.0)) / ( n * n - 2 * m));
        //cout<<"x = "<<x<<endl;
        double r, rr;
        r = ceil(n/x);
        rr = floor(n/x);
        long long md = n;
        double cal = ( (n*n) - (md%x)*(r*r) - (x - md%x)*(rr*rr));
        //cout<<cal/2.0<<endl;
        while((cal/2.0) < m) {
            x++;
            r = ceil(n/x);
            rr = floor(n/x);
            cal = ( (n*n) - (md%x)*(r*r) - (x - md%x)*(rr*rr));
            //cout<<cal/2.0<<endl;
        }
        cout<<x<<endl;
    }
        return 0;
}

Clique C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());
        int[][] arr = new int[n][];
        for(int i = 0; i < n; i++) {
            string[] ar_temp = Console.ReadLine().Split(' ');
            arr[i] = Array.ConvertAll(ar_temp,Int32.Parse);
            int low = 0;
            int high = arr[i][0];
            while (low + 1 < high) {
                int mid = (low + high) / 2;
                double r = getPoint(arr[i][0], mid);

                if (r < arr[i][1]) {
                    low = mid;
                }
                else {
                    high = mid;
                }
            }
            Console.WriteLine(high);
        }
    }
    
    static double getPoint(int n, int j) {
        if(j < 1) {
            j = 1;
        }
        int k = n % j;
        return 0.5d * (n * n - k * (n / j + 1) * (n / j + 1)  - (j - k) * (n / j) * (n / j));
    }
}

Clique Java Solution

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

public class Solution {

  // N.B. The hint provides us with the upper bound estimate, but not the real number of edges in
  // Turan graph
  static double turan(int n, int k) {
    k--;
    if (k < 1) return 0;
    double result = Math.pow(n, 2);
    result -= n % k * Math.pow(Math.ceil((double) n / (double) k), 2);
    result -= (k - n % k) * Math.pow(Math.floor((double) n / (double) k), 2);
    return 0.5 * result;
  }

  static int bsearch(int v, int e, int start, int finish) {
    if (start == finish) return start;
    int center = start + (finish - start) / 2;
    double minEdges = turan(v, center);
    if (minEdges == e) return center;
    if (minEdges < e) return bsearch(v, e, center + 1, finish);
    else return bsearch(v, e, start, center == start ? center : center - 1);
  }

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

    for (int t = 0; t < T; t++) {
      int V = scanner.nextInt();
      int E = scanner.nextInt();

      int estimate = bsearch(V, E, 1, V);

      if (turan(V, estimate) < E) estimate++;
      if (turan(V, estimate) >= E) estimate--;

      System.out.println(estimate);
    }
  }
}

Clique JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function (inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function () {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'clique' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. INTEGER m
 */

function clique(n, m) {
    const MAX_EDGES = n * (n - 1) / 2;
    function getEstimateEdges(n, r) {
        let mod = (n % r), ceil = Math.ceil(n / r), floor = Math.floor(n / r);

        return MAX_EDGES - mod * ceil * (ceil - 1) / 2 - (r - mod) * floor * (floor - 1) / 2;
    }

    if (m >= MAX_EDGES)
        return n;

    let r = 1;
    while (m > getEstimateEdges(n, r))
        r++;

    return r;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine().trim(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

        const n = parseInt(firstMultipleInput[0], 10);

        const m = parseInt(firstMultipleInput[1], 10);

        const result = clique(n, m);

        ws.write(result + '\n');
    }

    ws.end();
}

Clique Python Solution

import math
def  f(n,r):
    if r!=1:
        n2=n*n

        nmr=n%r
        return 0.5*(n2-(nmr)*(math.ceil(n/r))**2 - (r-(nmr))*(math.floor(n/r)**2))
    else:
        return 1
def binary(n,m):
    low=1
    high=n
    if f(n,n)<=m:
        return n
    while(low+1<high):
        mid=int((low+high)/2)
        r=f(n,mid)
        if r<m:
            low=mid
        else:
            high =mid
    return high
        
t=int(input())
for _ in range(t):
    n,m=map(int,input().split())

    r=binary(n,m)
    if r<n and f(n,(r+1))<=m:
        r=r+1
    if r<n and f(n,(r+1))<=m:
        r=r+1
    print(r)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python