Created
October 30, 2016 22:50
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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