CONCEPTS USED:
Hashing, Basic Mathematics
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT
(SIMPLIFIED
):
Given an array of
Nintegers, print the value of all those elements, whose indexes form an increasing
Arithmetic Progressionalong with the difference in
Arithmetic Progression. If an element occurs single time then print
0as difference.
See original problem statement here
For Example:
Input: N = 8 A[] = [4, 2, 4, 3, 4, 2, 4, 5] Output: 4 2 4 3 0 4 2 5 0 Explanation: 2 is present at index 1 and 5 which forms an A.P. with common difference 4 3 is present only at index 3 which is again an A.P. with common difference 0 4 is present at index 0, 2, 4, and 6 which forms an A.P. with common difference 2 5 is present only at index 7 which is again an A.P. with common difference 0
SOLVING APPROACH:
-
It can be easily solved in
Linear Time Complexityi.e.
O(N)but taking additional
O(N)space.
-
Traverse the array and keep putting the elements into a
set.
A
setis a data structure that contains unique elements.
-
Maintain two different arrays for
difference valueand
last valueof an element and keep updating them.
-
If the updated
difference valuedoes not matches the old value, this implies that the indices of this element are not in
Arithmetic Progression. Therefore remove the element from the set.
-
Finally print the elements and their
difference valuefrom the set.
ILLUSTRATION:
A[] = [4, 2, 4, 3, 4] i = 0 set = { } A[0] = 4 is not present in set, insert it set = {4} diff[4] = 0 last_index[4] = i = 0 i++; i = 1 A[1] = 2 is not present in set, insert it set = {2, 4} diff[2] = 0 last_index[2] = i = 1 i++; i = 2 A[2] = 4 is present in set, update last_index and difference diff[4] = i - last_index[4] = 2 - 0 = 2 last_index[4] = i = 2 i++; i = 3 A[3] = 3 is not present in set, insert it set = {2, 3, 4} diff[3] = 0 last_index[3] = i = 3 i++ ; i = 4 A[4] = 4 is present in set, update last_index and difference (if updated diff is not equal to previous diff, erase this element) diff[4] = i - last_index[4] = 4 - 2 = 2 last_index[4] = i = 4 Now print all elements of set along with their differences set = {2, 3, 4} 3 (size of set) 2 0 (diff[2]) 3 0 (diff[3]) 4 2 (diff[4])
SOLUTIONS:
#include
int a1[100001],a2[100001]; int b1[100001]; int main() { int n,a,o=0; scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&a); if(b1[a]) continue; if(a1[a]) { if(!a2[a]) a2[a]=i-a1[a]; else if(a2[a]!=i-a1[a]) { b1[a]=1;--o; } } else ++o; a1[a]=i; } printf("%d\n",o); for(int i=1;i<100001;++i) if(a1[i]&&!b1[i]) printf("%d %d\n",i,a2[i]); }
#include
using namespace std; typedef long long int ll; int main(){ ll n,a; cin>>n; ll diff[100005]={0},last_value[100005]={0}; bool b[100005]; sets; memset(b,false,sizeof(b)); for(ll i=1;i<=n;i++){ cin>>a; if(!b[a]){ s.insert(a); b[a]=true; } else{ if(diff[a]&&(i!=diff[a]+last_value[a])){ s.erase(a); } diff[a]=i-last_value[a]; } last_value[a]=i; } cout<
import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int ages[] = new int[n]; for(int i=0;i= ageB) continue; if (ageA < ageB) continue; if (ageA < 100 && 100 < ageB) continue; ans += countA * countB; if (ageA == ageB) ans -= countA; } } System.out.println(ans); } }
n = int(input()) l = list(map(int,input().split())) diff = [0 for i in range(100005)] last_value = [0 for i in range(100005)] b = [False for i in range(100005)] s = set() for i in range(1,n+1): a = l[i-1] if not b[a]: s.add(a) b[a] = True else: if diff[a] and i != diff[a] + last_value[a]: s.discard(a) diff[a]=i-last_value[a] last_value[a]=i print(len(s)) for it in s: print(it, diff[it])
[forminator_quiz id="405"]
This article tried to discuss Hashing, Basic Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing, Basic Mathematics you can check out MYCODE | Competitive Programming.