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}