HackerEarth Cost of Data problem solution

In this HackerEarth Cost of Data problem solution, Strings can be efficiently stored as a data structure, have efficient searching methods.

A new startup is going to use this method, but they don't have much space. So they want to check beforehand how much memory will be required for their data.

The following method describes the way in which this startup's engineers save the data in the structure.

Suppose they have 5 strings/words: et,eq,bd,be,bdp

An empty node is kept, and strings are inserted into the structure one by one.

Initially, the structure is this:

NULL

After inserting "et", the structure is this:

NULL

 |

 e

 |

 t

After inserting "eq", the structure is this:

   NULL

   /

  e

 / \

t   q

After inserting "bd", the structure is this:

   NULL

   /  \

  e    b

 / \    \

t   q    d

After inserting "be", the structure is this:

     NULL

   /     \

  e       b

 / \     / \

t   q   e   d

After inserting "bdp", the structure is this:

    NULL

   /     \

  e       b

 / \     / \

t   q   e   d

             \

              p

Therefore a total of 8 nodes are used here.

HackerEarth Cost of Data problem solution.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<cassert>
#include<sstream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
LL foo(string a, string b)
{
    int i;
    for(i=0; i<b.size(); i++)
        if(i>=a.size() || b[i]!=a[i])break;
    return (LL)((LL)(a.size())-i);
}
int main()
{
    int n,i,j;
    LL ans=1;
    string ar[100009];
    sd(n);
    for(i=0; i<n; i++)
        cin >> ar[i];
    sort(ar,ar+n);
    ans+=ar[0].size();
    for(i=1; i<n; i++)
        ans+=foo(ar[i],ar[i-1]);
    cout << ans << endl;
    return 0;
}