HackerRank Iterate It problem solution

In this HackerRank Iterate It problem solution, we have given the values of N and array A and need to computer and print the final value of rep after the pseudocode terminates, and if the loop will never terminate print -1 instead.

Problem solution in Python.

#!/bin/python3

import os
import sys

from math import gcd
from functools import reduce

#
# Complete the iterateIt function below.
#
# Note: didn't find any good pattern, so going for brute force (iterate and count)
#
def iterateIt(arr):
    remove_gcd(arr)
    n = a2b(arr)
    steps=0
    while n>0:
        kp = known_pat(n)
        if kp >= 0 : return steps + kp
        steps +=1
        n = iterate(n)
    return steps

def remove_gcd(arr):
    """Transform [a*i+b, i=i0<i1<i2...] to [i0-k,i1-k,i2-k, ... where k=i0-1]"""
    arr[:] = list(set(arr)) # remove duplicates and sort in place
    arr.sort()
    l = len(arr)
    if l>=2:
        a = reduce(gcd,(arr[i+1]-arr[i] for i in range(l-1)))
        b = arr[0] % a
        k = (arr[0]-b)//a - 1
        for i in range(l): arr[i] = (arr[i]-b)//a - k
    elif len(arr) == 1:
        arr[0]==1
    return

def a2b(arr):
    """Transform array of indices (1-based) to bitvector (0-based)."""
    n=0
    for i in arr: n |= 1<<(i-1)
    return n

def b2a(n):
    """Inverse of a2b(), used for debugging."""
    arr,i = [],1
    while n>0:
        b,n=n&1,n>>1
        if b: arr.append(i)
        i+=1
    return arr
    
def known_pat(n):
    """Check for patterns with known number of steps."""
    l = n.bit_length()
    if l>=3:
        #   [1, ....., n-1, n] => n steps needed
        if n & 1<<l-2 and n & 1: return l
    # this is for Testcase 26: [k,n-k,n] = [k,k+n%k,2k+n%k] + (n//k-2) steps
    if l>30:
        for k in range(2,10): # remember that bitvector is 0-based, not 1-based
            if n & 1<<(k-1) and n & 1<<l-1-k and (n == 1<<l-1|1<<l-1-k|1<<k-1):
                return l//k - 2 + iterateIt([k,k+l%k,2*k+l%k])
    return -1

def iterate(n):
    s=0
    while n>0:
        b,n=n&1,n>>1
        if b: s |=n
    return s
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    a_count = int(input())

    a = list(map(int, input().rstrip().split()))

    result = iterateIt(a)

    fptr.write(str(result) + 'n')

    fptr.close()

Problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    private static final int l = 60000;
    
    private static int gcd(int a, int b){
        if (a < b) return gcd(b, a);
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        boolean[] list = new boolean[l+1];
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++){
            int a = in.nextInt();
            set.add(a);
            list[a] = true;
        }
        boolean[] nList = new boolean[l+1];
        for (int e : set){
            for (int i = 1; i + e < l; i++){
                nList[i] |= list[i + e];
                
            }
        }
        list = nList;
        int g = 0;
        int min = -1;
        int max = 0;
        
        set.clear();
        for (int i = 0; i < l+1; i++){
                if (list[i]){
                    //System.out.println(a);
                    set.add(i);
                    if (min < 0) min = i;
                    max = i;
                    g = gcd(i, g);
                }
        }
        
        int o = 1;
        if (set.size() == 0){
            System.out.println(o);
            return;
        }
        Set<Integer> nSet = new HashSet<Integer>();
        for (int a : set)
            nSet.add(a / g);
        set = nSet;
        min /= g;
        max /= g;
        list = new boolean[l+1];
        for (int a : set)
            list[a] = true;
        while (min > 1){
            nList = new boolean[l+1];
            for (int a = min; a <= max; a++){
                if (list[a]){
                    for (int k = 1; k + a < l; k++){
                        nList[k] |= list[k + a];
                    }
                }
            }
            list = nList;
            max -= min;
            for (int a = 1; a <= max; a++){
                if (list[a]){
                    min = a;
                    break;
                }
            }
            o++;
        }
        System.out.println(o + max);
    }
    
}

Problem solution in C++.

#include <bits/stdc++.h>
#pragma warning(disable : 4996)

using namespace std;

int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}

int n, a[100009]; bool c[50009];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), c[a[i]] = true;
    int ret = 0;
    while (true) {
        vector<int> v;
        for (int i = 1; i <= 50000; i++) {
            if (c[i]) v.push_back(i), c[i] = false;
        }
        if (!v.size()) {
            break;
        }
        int g = v[0];
        for (int i = 1; i < v.size(); i++) {
            g = gcd(g, v[i]);
        } 
        for (int i = 0; i < v.size(); i++) {
            v[i] /= g;
        } 
        bool flag = true;
        for (int i = 0; i < v.size(); i++) {
            if (v[i] != i + 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ret += v.size();
            break;
        }
        for (int i = 0; i < v.size(); i++) {
            for (int j = i + 1; j < v.size(); j++) {
                c[v[j] - v[i]] = true;
            }
        }
        ret++;
    }
    printf("%dn", ret);
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef unsigned int uint;

#define MAX_N 100000
#define MAX_VALUE 50000

uint a[MAX_N];
bool b[MAX_VALUE+1];

int main() {
   
    uint n;
    scanf("%u", &n);
    assert(n <= MAX_N);
    for (int i = 0; i < n; i++) {
        uint v;
        scanf("%u", &v);
        assert(v);
        assert(v <= MAX_VALUE);
        b[v] = true;
    }
    
    
    uint rep = 0;
    while (true) {
        
        uint stride = 0;
        bool in_stride = true;
        n = 0;
        for (uint i = 1; i <= MAX_VALUE; i++) {
            if (b[i]) {
                b[i] = false;
                if (!n) {
                   stride = i;
                } else if (in_stride && i - a[n-1] != stride) {
                    in_stride = false;
                }
                a[n++] = i;
            }
        }
        if (!n) {
            break;
        }
        if (in_stride) {
            
            assert(a[n-1]/stride == n);
            rep += n;
            break;
        }
        rep++;
        for (uint ai = 0; ai < n-1; ai++) {
            for (uint aj = ai+1; aj < n; aj++) {
                
                b[a[aj] - a[ai]] = true;
            }
        }
    }
    printf("%un", rep);
    return 0;
}