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("%d\n", 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("%u\n", rep);
return 0;
}
0 Comments