Created
March 10, 2018 00:00
-
-
Save jianminchen/6c0b2f4053b98856f3aabcb20e4788b0 to your computer and use it in GitHub Desktop.
Walmart lab code sprint 2016 - interesting Fibonacci sum - one of submissions - created on March 9, 2018
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