Skip to content

GDP comparison of India with other countries

GDP comparison of India, USA, China, Japan, Russia of past few decades. Look at the GDP history on linear scale rather than log scale. China really took off in 2000 and now has covered half the distance needed to overtake US GDP. Japan’s GDP has not grown at all in past 20 years or so. Perhaps the reasons are 1) Missing software bus 2) Fixed population, with no immigration like US? Right/wrong anything else?

https://www.wolframalpha.com/input/?i=gdp+of+china+vs+india+vs+usa+vs+russia+vs+japan

Now look at this GDP per capita comparison of US, Japan, China, India:

https://www.wolframalpha.com/input/?i=gdp+per+capita+india+vs+china+vs+usa+vs+japan+vs+russia

Over here Japan is still doing quite well. As their population is the same, perhaps. Just dipped a bit, in recent years.
China has become Russia level.
India has improved, but to a very less extent.

Note: Please see GDP history on linear scale rather than log scale.

PS: Why do they still teach French at school? Should offer Mandarin. No?

Advertisements

Codility – Dynamic programming Number Solitaire

The problem is the following:

A game for one player is played on a board consisting of N consecutive squares, numbered from 0 to N − 1. There is a number written on each square. A non-empty array A of N integers contains the numbers written on the squares. Moreover, some squares can be marked during the game.

At the beginning of the game, there is a pebble on square number 0 and this is the only square on the board which is marked. The goal of the game is to move the pebble to square number N − 1.

During each turn we throw a six-sided die, with numbers from 1 to 6 on its faces, and consider the number K, which shows on the upper face after the die comes to rest. Then we move the pebble standing on square number I to square number I + K, providing that square number I + K exists. If square number I + K does not exist, we throw the die again until we obtain a valid move. Finally, we mark square number I + K.

After the game finishes (when the pebble is standing on square number N − 1), we calculate the result. The result of the game is the sum of the numbers written on all marked squares.

For example, given the following array:

A[0] = 1
A[1] = -2
A[2] = 0
A[3] = 9
A[4] = -1
A[5] = -2
one possible game could be as follows:

the pebble is on square number 0, which is marked;
we throw 3; the pebble moves from square number 0 to square number 3; we mark square number 3;
we throw 5; the pebble does not move, since there is no square number 8 on the board;
we throw 2; the pebble moves to square number 5; we mark this square and the game ends.
The marked squares are 0, 3 and 5, so the result of the game is 1 + 9 + (−2) = 8. This is the maximal possible result that can be achieved on this board.

Write a function:

func Solution(A []int) int

that, given a non-empty array A of N integers, returns the maximal result that can be achieved on the board represented by array A.

For example, given the array

A[0] = 1
A[1] = -2
A[2] = 0
A[3] = 9
A[4] = -1
A[5] = -2
the function should return 8, as explained above.

Assume that:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−10,000..10,000].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution:

Algo: We use Dynamic programming. Here’s a good blog to learn it.

Basically, we start from the destination position, and consider moves to that from 6 places behind. And then move back, and check for the best way to move to the target with max val. We come back this way to position ‘0’ and then simply return dp_arr[0].

Below’s the code :

package solution

// you can also use imports, for example:
// import “fmt”
// import “os”

// you can write to stdout for debugging purposes, e.g.
// fmt.Println(“this is a debug message”)

func Solution(A []int) int {
// write your code in Go 1.4

N := len(A)

dp_arr := make([]int, N)
dp_arr[N-1] = A[N-1]

for i := N – 2; i >= 0; i– {
var max int
for j := 1; j = N {
break
}
if j == 1 || dp_arr[i+j] > max {
max = dp_arr[i+j]
}
}
dp_arr[i] = A[i] + max
}

return dp_arr[0]
}

A rather short piece of code, for a problem, which may look daunting in the first go. And this scores 100% on codility. Works in O(N) time.

Codility – MaxCounters

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

func Solution(N int, A []int) []int

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

a structure Results (in C), or
a vector of integers (in C++), or
a record Results (in Pascal), or
an array of integers (in any other programming language).
For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].
Complexity:

expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution: If we do it without thinking of time complexity, we will get a O(N*M) solution. But the problem wants a O(N+M) solution. So first we loop for M, to find all the max ops, and the max value of the last max_op. Taking into account the inc() operations on a same position, to compute thread max (local max)

After that, we loop for the remaining of N, after having initialized the counters to max vals. And just do the counter ops

Code:

package solution

// you can also use imports, for example:
// import “fmt”
// import “os”

// you can write to stdout for debugging purposes, e.g.
// fmt.Println(“this is a debug message”)

func Solution(N int, A []int) []int {
// write your code in Go 1.4

global_max := 0
global_max_pos := -1
thread_max := 0
my_map := make(map[int]int)
for i, v := range A {
if v <= N {
count, ok := my_map[v]
if !ok {
my_map[v] = 1
if thread_max < 1 {
thread_max = 1
}
} else {
tmp := count + 1
my_map[v] = tmp
if thread_max < tmp {
thread_max = tmp
}
}
} else {
global_max += thread_max
global_max_pos = i
// reset
my_map = make(map[int]int)
thread_max = 0
}
}

ret := make([]int, N)

for i := 0; i < N; i++ {
ret[i] = global_max
}

for i := global_max_pos + 1; i < len(A); i++ {
ret[A[i]-1]++
}
return ret
}

It works in O(N+M) and scores 100% on codilty.

Codility – ladder

The problem:

You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:

with your first step you can stand on rung 1 or 2,
if you are on rung K, you can move to rungs K + 1 or K + 2,
finally you have to stand on rung N.
Your task is to count the number of different ways of climbing to the top of the ladder.

For example, given N = 4, you have five different ways of climbing, ascending by:

1, 1, 1 and 1 rung,
1, 1 and 2 rungs,
1, 2 and 1 rung,
2, 1 and 1 rungs, and
2 and 2 rungs.
Given N = 5, you have eight different ways of climbing, ascending by:

1, 1, 1, 1 and 1 rung,
1, 1, 1 and 2 rungs,
1, 1, 2 and 1 rung,
1, 2, 1 and 1 rung,
1, 2 and 2 rungs,
2, 1, 1 and 1 rungs,
2, 1 and 2 rungs, and
2, 2 and 1 rung.
The number of different ways can be very large, so it is sufficient to return the result modulo 2P, for a given integer P.

Write a function:

func Solution(A []int, B []int) []int

that, given two non-empty arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2B[I].

For example, given L = 5 and:

A[0] = 4 B[0] = 3
A[1] = 4 B[1] = 2
A[2] = 5 B[2] = 4
A[3] = 5 B[3] = 3
A[4] = 1 B[4] = 1
the function should return the sequence [5, 1, 8, 0, 1], as explained above.

Assume that:

L is an integer within the range [1..50,000];
each element of array A is an integer within the range [1..L];
each element of array B is an integer within the range [1..30].
Complexity:

expected worst-case time complexity is O(L);
expected worst-case space complexity is O(L) (not counting the storage required for input arguments).

Solution: Screen cap of sublime text, below. Has all the code. It uses fibonacci series. It is so because no. of unique ways of climbing upto a step N, is sum of no. of unique ways of upto its two previous rungs. The code comment (in the screen grab, explains the reason.

codility_ladder_code

Also, the above solution, worked (100%, Yay!) in the first try. Results below.

codility_ladder

Codility – common prime divisors

Algorithm:
For each pair of numbers in the list:

1) First find the GCD of the given pair of numbers
2) Do some boundary checks like at least one number greater than 1 and also GCD greater than 1 (Note GCD of 1 denotes, that there are no common prime divisors)
3) Now take the remainder of each number by dividing by GCD.
4) Take the GCD of the remainder with the GCD got in step 1. If the new GCD is 1 then discard this pair, as it shows no common divisors.
Logic: The GCD is of the form p1^x1*p2^x2…pn^xn, for prime numbers p1 through pn, and x1..xn are in the set [1…Z], Z is greater than 1. So if we get a remainder, which does not share a single prime number with the GCD1 then, it means the prime divisors are not the same of the two numbers.
5) If all stages pass increment the result count, as by now we are sure that the two given numbers have the same prime divisors.

package main

// you can also use imports, for example:
import “fmt”

// import “os”
import “math”

// you can write to stdout for debugging purposes, e.g.
// fmt.Println(“this is a debug message”)

func Solution(A []int, B []int) int {
// write your code in Go 1.4

N := len(A)

ret := 0

for_label:
for i := 0; i min_ab {
continue
}

if gcd1 == 1 && min_ab > 1 {
continue
}

arem := a / gcd1
for arem > 1 {
gcd2 := gcd(arem, gcd1)
if gcd2 == 1 {
continue for_label
}
arem /= gcd2
}
brem := b / gcd1
for brem > 1 {
gcd2 := gcd(brem, gcd1)
if gcd2 == 1 {
continue for_label
}
brem /= gcd2
}
fmt.Printf(“a: %v, b: %v\n”, a, b)
ret++
}

return ret
}

// Greatest common divisor
func gcd(a, b int) int {
if a == b {
return a
} else if a > b {
if a%b == 0 {
return b
}
return gcd(a%b, b)
} else {
if b%a == 0 {
return a
}
return gcd(a, b%a)
}
}

func main() {
var A []int
var B []int
for i := 1; i < 71; i++ {
for j := 1; j < 71; j++ {
A = append(A, i)
B = append(B, j)
}
}

fmt.Printf("No. of pairs: %v\n", len(A))

ret := Solution(A, B)
fmt.Printf("Result: %v\n", ret)
}

common_prime_divisor

Codility – count not divisible problem

I like this solution, as it came out simple and elegant. The solution is based on Sieve of Eratosthenes. A variation actually, as had to build only based on numbers available.

package solution

// you can also use imports, for example:
//import “fmt”

// import “os”
//import “sort”

// you can write to stdout for debugging purposes, e.g.
// fmt.Println(“this is a debug message”)

func Solution(A []int) []int {
// write your code in Go 1.4

N := len(A)

mymap := make(map[int]int)
for i := 0; i < N; i++ {
_, ok := mymap[A[i]]
if !ok {
mymap[A[i]] = 1
} else {
mymap[A[i]] += 1
}
}

// construct a custom Eratosthenes sieve
// of factors
// Note we create a custom sieve based on numbers we have
// in the map created above
sieve := make([]int, 2*N+1)
for i := 1; i <= 2*N; i++ {
v, ok := mymap[i]
if ok {
for k := i; k <= 2*N; k += i {
sieve[k] += v
}
}
}

// Now we have every thing computed in the sieve,
// with the help of the sieve.
// We just loop again,
// and return the values from the sive

ret := make([]int, N)
for i := 0; i < N; i++ {
ret[i] = N – sieve[A[i]]
}

return ret

}

And yes, this too got 100% result. Yay!
codility-count-not-divisible

Codility – Peaks

This problem is under the learning lesson “Prime and Composite numbers” . I am trying to do all the problems marked as Respectable. Here’s my solution for this one:

package solution

// you can also use imports, for example:
//import “fmt”

// import “os”
//import “math”

// you can write to stdout for debugging purposes, e.g.
// fmt.Println(“this is a debug message”)

func Solution(A []int) int {
// write your code in Go 1.4
N := len(A)
var peaks []int
num_peaks := 0
for i := 1; i A[i-1] && A[i] > A[i+1] {
peaks = append(peaks, i)
num_peaks++
}
}

if num_peaks == 0 {
return 0
}

for parts := num_peaks; parts >= 1; parts– {
if N%parts != 0 {
continue
}
k := N / parts
//fmt.Printf(“k: %v\n”, k)
peak_ind := 0
cur_peak := peaks[peak_ind]
//fmt.Printf(“cur_peak: %v\n”, cur_peak)
peak_missing := false
for i := 0; i+k-1 = i && cur_peak < i+k && peak_ind < num_peaks {
// peak found in block
peak_found = true
peak_ind++
if peak_ind < num_peaks {
cur_peak = peaks[peak_ind]
//fmt.Printf("cur_peak: %v\n", cur_peak)
}
}

//fmt.Printf("block %v, peak_found: %v\n", i, peak_found)
if !peak_found {
peak_missing = true
break
}
}

if !peak_missing {
return parts
}
}

return 0
}

Was glad to get Another 100% result. Albeit, in my 2nd try.
codility_peaks_2