Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created October 30, 2016 22:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/b74fdea146fdf793fe9c3661a9bda793 to your computer and use it in GitHub Desktop.
Save jianminchen/b74fdea146fdf793fe9c3661a9bda793 to your computer and use it in GitHub Desktop.
HackerRank - Fibonacci sum - try to solve out-of-memory issue, timeout issues - second submission
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace InterestingFibonacciSum
{
class InterestingFibonacciSum_OutofMemory
{
/*
* https://www.hackerrank.com/contests/walmart-codesprint-algo/challenges/fibonacci-sum-1
* Oct. 29, 2016
* Spent two hours to read problem statement
* 11:30am - 1:30am
*
* 7:12pm - start to write some code
* Figure out things in detail
*
* 9:12pm complete the coding
* 9:12pm put into HackerRank to test the code
*
*/
static void Main(string[] args)
{
//testing3();
process();
}
private static void testing1()
{
int n = 2;
int[] arr = { 1, 1 };
// int result = calculate(n, arr);
}
private static void testing2()
{
int n = 3;
int[] arr = { 1, 2, 3 };
// int result = calculate(n, arr);
}
private static void testing3()
{
int n = 100000;
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = i + 1;
int result = calculate(n, arr);
}
/*
* 9:33pm
* first, test the function is working
* ignore out-of-memory issue
*/
private static void process()
{
int q = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < q; i++)
{
int n = Convert.ToInt32(Console.ReadLine()); // 10^5 upper limit, size of array
int[] arr = new int[n];
arr = cToInt(Console.ReadLine().Split(' '));
Console.WriteLine(calculate(n, arr));
}
}
/*
* start: 7:15pm
* end: 7:19pm
*/
private static int[] cToInt(string[] arr)
{
if (arr == null || arr.Length == 0)
return new int[0];
int n = arr.Length;
int[] res = new int[n];
for (int i = 0; i < n; i++)
{
res[i] = Convert.ToInt32(arr[i]);
}
return res;
}
private static int calculate(int n, int[] arr)
{
int count = 0;
int[] sum1 = sumC(n, arr);
Dictionary<int, int> coll = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
int L = i;
int R = j;
int AL2R = (L == R) ? arr[L] : (sum1[R] - sum1[L] + arr[L]);
if (coll.ContainsKey(AL2R))
coll[AL2R]++;
else
coll.Add(AL2R, 1);
}
return count = fiboSmart(coll);
}
/*
* 8:25pm
* To reduce the variation of calculation from O(n^2) to O(n)
* sum(A) = sumC[R] - sumC[L]
*
* 8:40pm
* L, R two variable, each is O(n), so LR pair will be O(n^2)
* but, we use sumC to get the difference based on O(n) size array
*
* 8:55pm
* cut the size to 10^9 + 7
* module calculation
*/
private static int[] sumC(int n, int[] arr)
{
int[] sum = new int[n];
int module = 1000000000 + 7;
sum[0] = arr[0];
for (int i = 1; i < n; i++)
{
sum[i] = (sum[i - 1] + arr[i]) % module;
}
return sum;
}
/*
* 10:28pm
* start to work on the function
*
* 10:39pm
* came out an idea, and then implemented the code
*/
private static int fiboSmart(Dictionary<int, int> coll)
{
int SIZE = 1000000000 + 7;
int module = SIZE;
int[] chosen = coll.Keys.ToArray();
Array.Sort(chosen);
int len = chosen.Length;
int index = 0;
int tmp0 = 0;
if (index < len && chosen[index] == 0)
{
index++;
}
int count = 0;
int tmp1 = 1;
if (index < len && chosen[index] == 1)
{
int no = coll[1];
count = (count + no) % module;
index++;
}
int sum = 0;
for (int i = 2; i <= chosen[len-1]; i++)
{
sum = (tmp0 + tmp1) % SIZE;
if (index < len && chosen[index] == i)
{
int no = coll[i];
count = (count + no*sum) % module;
index++;
}
tmp0 = tmp1;
tmp1 = sum;
}
return count;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment